构造半平面莫队？/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;
}
原文地址：http://www.cnblogs.com/do-while-true/p/16815614.html
