ICPC澳门站 C – Laser Trap(计算几何)

发布于 2022-04-04  1307 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09