ICPC澳门站 C - Laser Trap（计算几何）

题目链接：C-Laser Trap_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com)

题目大意

T个测试用例，二维平面上N个点，形成的完全图。

问至少删除多少个点可以使得一个球在不碰到任何线的情况下从(0, 0)移动到(inf, inf)。

数据保证不存在任何一条线通过(0, 0)。

思路

哎，当时在赛场上想到了用斜率，用atan，也用了long double，但是没想到用atan2l(y, x)这个函数啊！这里需要学习一下这个新函数。

atan2l((long double)y, (long double)x)，返回值为long double，表示tan值为y / x的弧度，并且可以表示象限。注意如果本题用double会导致精度不够。

我们将N个点拓展成2 * N点，因为这里的点的顺序并非“偏序”的，举个例子，第二圈的第一象限的角度应该比第一圈第四象限的大，但是第一圈的第一象限的角比第一圈的第四象限的小。

也就是说我们要把每个点，都生成一个“位于第二圈的该点”，使得这个点可以比后面的一些点大，从而避免出现误差。

后面就用双指针来遍历一遍就行了，时间复杂度O(N)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long double PI = acosl(-1);
const int maxn = 2e6 + 9;
 
long double p[maxn];

void solve()
{
	int N;cin >> N;//构造2 * N个点
	//新函数atan2(y, x);可以用于确定某个点的角度，同时可以确定象限
	for(int i = 1;i <= N; ++ i)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		p[i] = atan2l(1.0 * y, 1.0 * x);	
	}
	sort(p + 1,p + 1 + N);
	for(int i = 1;i <= N; ++ i)p[i + N] = p[i] + 2 * PI;
	int ans = N;
	for(int i = 1, j = 1;i <= N; ++ i)
	{
		while(j <= 2 * N && p[j] - p[i] < PI)++ j;
		ans = min(ans, j - i - 1);
	}
	printf("%lld\n",ans);
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();
	return 0;
}