题目

给定 \(n\) 个互异的整点 \(\{(x_k,y_k)\}_{k=1}^n\)，和 \(m\) 个点集 \(\{S_k=\{(x,y)|A_kx+B_ky+C_k>0\}\}_{k=1}^{m}\)，请给出一个排列 \(p\in S_m\)，使得 \(|S_{p_1}|+\sum_{k=2}^{m}|S_{p_k}\oplus S_{p_{k-1}}|\le M\)。其中 \(A\oplus B\) 表示 \(A,B\) 集合的对称差，可以理解为“对元素的出现情况异或”。

对于 \(100\%\) 的数据，满足 \(M=1.8\times 10^8,1\le n\le 10^5,1\le m\le 2\times 10^5\)，且 \(|A_k|,|B_k|,|C_k|,|x_k|,|y_k|\le 10^9,A_k^2+B_k^2>0\)。

理论上来说，这是 2021 昆明区域赛的 H 题。

分析

这个......看题，显然是做莫队啊......

实际上可以想象成：维护一个点集 \(S\)，每次只能加入或者删除单个元素。我们需要给半平面安排一个顺序，使得从 \(S=\varnothing\) 开始，按照这个顺序经过每个点集所需要的 \(S\) 的变化次数 \(\le M\)。

Note. 所以，莫队的本质实际上也就是一类维护难以成块更新的集合的分块方法。

建议画一个“莫队九宫格”

莫队的关键在于，对于元素分组，使得组内元素的移动次数尽可能降低（一般是降到线性于另一个量）。组间移动的次数可能也需要考虑，不过一般来说不会成为瓶颈。

如何分组才能使得组内移动次数尽可能少呢？或许可以类似于莫队，按照“截距”排序。emmmm......由于不可能按照斜率分组，所以按照截距排序没有办法保证点能够完全有序加入，这个还不够好。

另一个角度，我们考虑旋转。假如所有直线都经过同一个点，这样无疑是相当优秀的，组内移动只有 \(2n\) 次。

Remark. 从这个角度来看，几何之中不仅有平动，也有转动。看起来对于转动不够熟悉！

另外，这背后似乎有一个叫做 rotating scanline（旋转扫描线）的算法，不清楚怎么回事。

那么，假如从 \(n\) 个点中，选取了 \(B\) 个可能的旋转中心，我们显然对于每条半平面的分界直线，都选取离它最近的旋转中心。这样的话，我们实际上构建了这 \(B\) 个点的 Voronoi 图，理论上来说每个块内部的期望的点数为 \(O(\frac n B)\)。分析一下移动次数：

1. 每次旋转，按照斜率来旋转本身的移动次数为 \(O(n)\)。另外，每条直线并不是严格经过旋转中心，因此还需要从旋转中心移动到目标直线，这一部分移动次数为 \(O(\frac n B)\)。

   Note. 为了避免歧义，实际的移动方式就是在直线之间切换。这里假装是每次都要往返旋转中心，分析出来的步数不会小于真实步数。

2. 切换旋转中心，如果始末斜率相同，则移动次数就是 \(n\) 次。不过这里不会成为瓶颈，无所谓。

最终，我们的构造方法的移动次数应为 \(O(mB+\frac{n}B)\)，当 \(B\) 取到 \(\sqrt{\frac {n^2}m}\) 的时候，理论上来说是最优的。

代码

#include <cmath>
#include <cstdio>
#include <random>
#include <vector>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int MAXN = 1e5 + 5, MAXM = 2e5 + 5;

template<typename _T>
void read( _T &x ) {
	x = 0; char s = getchar(); int f = 1;
	while( ! ( '0' <= s && s <= '9' ) ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	x *= f;
}

template<typename _T>
void write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) write( x / 10 );
	putchar( x % 10 + '0' );
}

int seq[MAXN];

std :: vector<int> each[MAXN];

double A[MAXM], B[MAXM], C[MAXM], ang[MAXM];
double X[MAXN], Y[MAXN];

int N, M, THRE;

inline double GetDist( const double &a, const double &b, const double &c, const double &x, const double &y ) {
	return fabs( a * x + b * y + c ) / sqrt( a * a + b * b );
}

int main() {
	static std :: mt19937 rng( 1145141 );

	freopen( "c.in", "r", stdin );
	freopen( "c.out", "w", stdout );
	read( N ), read( M );
	rep( i, 1, N ) scanf( "%lf %lf", &X[i], &Y[i] );
	rep( i, 1, M ) {
		scanf( "%lf %lf %lf", &A[i], &B[i], &C[i] );
		ang[i] = atan2( - A[i], B[i] );
	}
	rep( i, 1, N ) seq[i] = i;
	std :: shuffle( seq + 1, seq + 1 + N, rng );
	THRE = ceil( sqrt( M ) );
	rep( i, 1, M ) {
		int idx = 1;
		double dist = GetDist( A[i], B[i], C[i], X[seq[1]], Y[seq[1]] );
		rep( j, 2, THRE ) {
			double tmp = GetDist( A[i], B[i], C[i], X[seq[j]], Y[seq[j]] );
			if( tmp < dist ) dist = tmp, idx = j;
		}
		each[idx].push_back( i );
	}
	rep( i, 1, THRE ) {
		std :: sort( each[i].begin(), each[i].end(),
			[] ( const int &a, const int &b ) -> bool {
				return ang[a] < ang[b];
			} );
		for( const int &x : each[i] )
			write( x ), putchar( '\n' );
	}
	return 0;
}