2825472_ac_0ms_96k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>

double R;
int n;
struct point
{
	double x, y;
};

point pt[1001], c;
int no;

double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int cross(point a,point b,point c)
{
	return (int)((c.x-b.x)*(a.y-b.y)-(a.x-b.x)*(c.y-b.y));
}

int max(int a,int b)
{
	return a<b?b:a;
}

int main()
{
	int i, j, tmp;
	int ans, l, r, mid;
	point t;

	while(scanf("%lf%lf%lf",&c.x,&c.y,&R)==3&&R>=0.0)
	{
		no = 0;ans = 0;
		scanf("%d",&n);
		while(n--)
		{
			scanf("%lf%lf",&t.x,&t.y);
			if(dis(t,c)<=R)
				pt[no++] = t;
		}
		for(i = 0; i < no; i++)
		{
			mid = l = r = 0;
			for(j = 0; j < no; j++)
			{
				tmp = cross(pt[i],c,pt[j]);
				if(tmp==0)
					mid++;
				else
					if(tmp>0)
						l++;
					else
						r++;
			}
			tmp = max(l,r)+mid;
			if(tmp>ans)
				ans = tmp;
		}
		printf("%d\n",ans);
	}
	return 0;
}