C++(clang++11) 解法, 执行用时: 57ms, 内存消耗: 432K, 提交时间: 2020-12-01 13:15:20

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 100;

struct node {
	int w;
	double ang;
	int id;
	bool operator<(const node &M) const {
		if (fabs(ang - M.ang) < 1e-12)
			return w < M.w;
		return ang < M.ang;
	}
} e[N];


bool vis[1010];
int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, d;
		cin >> n >> d;
		int cnt = 0;
		int id = 0;
		for (int i = 1; i <= n; i++) {
			double x, y;
			cin >> x >> y;
			if (x * x + y * y <= d * d + 1e-12)
				continue;
			double ang = atan2(y, x);
			double a = asin(1.0 * d / sqrt(x * x + y * y));
			id++;
			e[cnt++] = {0, fmod(ang - a + 4 * acos(-1), 2 * acos(-1)), id};
			e[cnt++] = {1, fmod(ang + a + 4 * acos(-1), 2 * acos(-1)), id};
		}

		if (cnt == 0)
			puts("1");
		else {
			sort(e, e + cnt);
			int ans = id;
			for (int i = 0; i < cnt; i++) {
				int num = 0;
				memset(vis, 0, sizeof vis);
				vector<int>vec;
				vec.clear();
				for (int k = 0; k < cnt; k++) {
					int j = (i + k) % cnt;
					if (e[j].w == 0) {
						vis[e[j].id] = 1;
						vec.push_back(e[j].id);
					}
					if (e[j].w == 1 && vis[e[j].id]) {
						num++;
						for (auto it : vec)
							vis[it] = 0;
						vec.clear();
					}
				}
				num += vec.size();
				ans = min(ans, num);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 480K, 提交时间: 2020-03-03 23:04:44

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct node {
	double x,y,l,r;
} p[505];
inline bool cmp(node a,node b) {
	return a.l<b.l;
}
const double pi=acos(-1);
double pl[505],pr[505],maxr[505],r;
int main() {
	int n,T,cnt,cnt2,ans,pos,tot;
	double d,dis,si,otg,t,tg;

	scanf("%d",&T);
	while(T--) {

		scanf("%d%lf",&n,&d),cnt=0;
		for (int x,y,i=1; i<=n; i++) {
			scanf("%d%d",&x,&y);
			dis=sqrt(x*x+y*y);
			if (dis<=d) continue;

			si=d/dis,otg=si/sqrt(1-si*si);
			t=atan(otg),tg=atan2(y,x);

			while(tg-t<0) tg+=2*pi;
			while(tg-t>2*pi) tg-=2*pi;
			p[++cnt]=(node) {
				x,y,tg-t,tg+t
			};
		}

		sort(p+1,p+cnt+1,cmp);

		if (cnt) {
			ans=cnt;
			for(int i=1; i<=cnt; i++) {
				cnt2=0;

				for (int j=i; j<=cnt; j++)
					pl[++cnt2]=p[j].l,pr[cnt2]=p[j].r;
				for (int j=1; j<i; j++)
					pl[++cnt2]=p[j].l+2*pi,pr[cnt2]=p[j].r+2*pi;

				pos=1,tot=0,maxr[cnt]=pr[cnt];
				for (int j=cnt-1; j; j--) maxr[j]=min(maxr[j+1],pr[j]);
				while(pos<=cnt) {

					r=maxr[pos];
					while(pos<=cnt && pl[pos]<=r) pos++;
					tot++;
				}
				ans=min(ans,tot);
			}
			printf("%d\n",ans);
		} else puts("1"); //由于病毒数n>=0，如果病毒到圆心距离<=d，至少需要一条直线
	}
}