题目链接: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; }
Comments NOTHING