题解 | #Nearest Point#

计算几何专题 —— 极角序H Nearest Point

题目大意求每个点是枚举点的最近点的概率是多少。转化一下就是一个平面中多少的弧度属于这个点最后除以2π。最近点在旋转的过程中会有如下变化： 可以发现最近点的转变是在某一关键位置发现了转变，只需要记录关键位置即可。即枚举点A，观察B，C点对于不同旋转角度，谁在x轴上的投影离A更近 旋转x轴，发现 1.x轴垂直于BC 2.设BC中点为D，x轴垂直于AD 共4种情况，BC的离A的远近关系发生变化 之后将关键位置进行极角排序，每次拿到相邻的两个向量，求得这两个向量之间是属于哪个点的区域。最后将这个点的区域加上弧度即可。至于如何求弧度以及如何判定谁更近有以下操作：

核心代码：

using point = Point<int>;
void solve()
{
	cout << fixed << setprecision(12);
	int n;
	cin >> n;
	vector<point> p(n);
	for(int i = 0 ; i < n ; i ++)
	{
		cin >> p[i];
		p[i] = p[i] * 2;//扩大两倍防止取中点有误差
	}

	auto work = [&](point &o , int id) -> void{
		vector<point> v;
		int idx = 0 , dis = 1e9;
		for(int i = 0 ; i < n ; i ++)
		{
			if(i == id) continue;
			if(dis > o.dis2(p[i]))
			{
				dis = o.dis2(p[i]);
				idx = i;
			}
			for(int j = i + 1 ; j < n ; j ++)
			{
				if(i == id || j == id) continue;
				point BC = p[i]&p[j];//pipj
				point AD = o&((p[i] + p[j])/2);
				if((AD ^ BC) == 0) continue;
              	//cos sin
				v.push_back(BC.rot(0,1));
				v.push_back(BC.rot(0,-1));
				v.push_back(AD.rot(0,1));
				v.push_back(AD.rot(0,-1));
			}
		}
		if(!v.size())
		{
			for(int i = 0 ; i < n ; i ++)
				cout << (idx == i) << " \n"[i==n-1];
			return;
		}
		sort(v.begin(),v.end(),argcmp<int>());
		v.push_back(v[0]);
		vector<double> ans(n);
		int m = v.size();//m最坏是n^2
		for(int i = 0 ; i + 1 < m ; i ++)
		{
			int j = i + 1;
			point w = v[i] + v[j];
			int cur = 1e9 , idx = -1;
			for(int k = 0 ; k < n ; k ++)
			{
				if(k == id) continue;
				if(cur > abs(w*(o&p[k])))
				{
					cur = abs(w*(o&p[k]));
					idx = k;
				}
			}
			double alpha = atan2l(v[i]^v[j],v[i]*v[j]);
			ans[idx] += alpha;
		}
		for(int i = 0 ; i < n ; i ++)
		{
			if(i == id) cout << 0 << " ";
			else cout << ans[i] / (PI*2)<< " ";
		}
		cout << endl;
	};	

	for(int i = 0 ; i < n ; i ++)
	{
		work(p[i],i);
	}
}