自动搬运

查看原文

来自洛谷，原作者为

	do_while_true 水

搬运于2025-08-24 22:39:53，当前版本为作者最后更新于2022-10-22 10:46:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

构造半平面莫队？/jk

注意到对于一个半平面的直线，通过平移和旋转经过的点数，一定大于等于它们的对称差，因为对称差中的点会被经过奇数次，不在对称差中的点会被经过偶数次。那么可以将问题转化成构造出一个移动直线的方案，使得经过给出的每个直线，而且使得经过的点尽可能的小。

考虑一个事实，如果现在半平面的直线绕着一个点只改变斜率进行旋转，只会经过 $\mathcal{O}(n)$个点。

那么首先先随机撒 $\mathcal{O}(\sqrt n)$ 个点，这样对于一个半平面的直线，它向下平移使得它遇上了第一个标记点，经过的点数期望是 $\mathcal{O}(\sqrt n)$ 的。那么将这个半平面挂在这个标记点上，构造一个移动直线的方案：

首先从上一个标记点移动到当前标记点，然后把这个标记点上挂的半平面极角排序，一个个扫，先旋转得到应该具有的斜率，然后平移得到应该具有的截距，再平移回标记点，以此类推。

由于只有 $\mathcal{O}(\sqrt n)$ 标记点，每次标记点之间移动最多经过 $\mathcal{O}(n)$ 个点，所以这部分经过点数 $\mathcal{O}(n\sqrt n)$ 个；在每个标记点处进行旋转，经过的点也是 $\mathcal{O}(n)$ 个；标记点向挂着的半平面平移的时候，根据前面的结论，对于每个半平面是经过期望 $\mathcal{O}(\sqrt n)$ 个点。所以总的经过点数是 $\mathcal{O}((n+m)\sqrt n)$．

看上去常数很大，不过要考虑到实际上对称差的和是小于等于经过的点数，而且似乎也很难构造数据卡掉它，于是它还挺优秀的（

洛谷不知道为什么后面的点 UKE 了，还是从牛客交吧。

mt19937 rnd(time(NULL)^(ull)(new char));
const int N=200010;
int n,m,p[N],B;
ll x[N],y[N],a[N],b[N],c[N];
vector<pair<double,int>>vec[N];
signed main(){
	read(n,m);
	B=min(n,450);
	for(int i=1;i<=n;i++){
		read(x[i],y[i]);
		p[i]=i;
	}
	shuffle(p+1,p+n+1,rnd);
	for(int i=1;i<=m;i++){
		read(a[i],b[i],c[i]);
		int pos=0;
		ll mx=0;
		for(int j=1;j<=B;j++){
			ll o=a[i]*x[p[j]]+b[i]*y[p[j]]+c[i];
			if(o>0){
				if(!pos || o<mx){
					pos=j;
					mx=o;
				}
			}
		}
		if(!pos)pos=1;
		vec[pos].pb(mp(atan2(a[i],b[i]),i));
	}
	for(int i=1;i<=B;i++){
		sort(vec[i].begin(),vec[i].end());
		for(auto j:vec[i])cout << j.se << '\n';
	}
	return 0;
}