【SSL_1232】雷达覆盖

思路：

以一个点作为平角，计算几何统计

c o d e code code

#include<iostream>
#include<cstdio>
#include<cmath> 
#include<cstring>

using namespace std;

long long n, ans;
long long xx, yy;
long long x[101010], y[101010];
bool v[101010];
double rr;

double dis(double x1, double y1, double x2, double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double js(double x1, double y1, double x2, double y2)
{
	return x1*y2-x2*y1;
}

int main()
{
	while(scanf("%lld%lld%lf", &xx, &yy, &rr))
	{
		if(rr<0)
			return 0;
		memset(v, 0, sizeof(v));
		scanf("%lld", &n);
		for(int i=1; i<=n; i++)
		{
			scanf("%lld%lld", &x[i], &y[i]);
			if(dis(xx*1.0, yy*1.0, x[i]*1.0, y[i]*1.0)>rr)
				v[i]=1;
		}
		for(int i=1; i<=n; i++)
		{
			long long l=0, r=0;
			if(v[i])
				continue;
			for(int j=1; j<=n; j++)
			{
				if(v[j])
					continue;
				if(js(xx-x[i], yy-y[i], x[j]-x[i], y[j]-y[i])<=0)
					r++;
				if(js(xx-x[i], yy-y[i], x[j]-x[i], y[j]-y[i])>=0)
					l++;
			}
			ans=max(ans, max(l, r));
		}
		printf("%lld\n", ans);
		ans=0;
	}
	return 0;
}
/*
25 25 3.5
7
25 28
23 27
27 27
24 23
26 23
24 29
26 29
350 200 2.0
5
350 202
350 199
350 198
348 200
352 200
995 995 10.0
4
1000 1000
999 998
990 992
1000 999
*/