首页 > 代码库 > POJ 1106

POJ 1106

先判断是否在圆内,然后用叉积判断是否在180度内。枚举判断就可以了。。。

感觉是数据弱了。。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const double eps=0.00000001;struct point{	double x,y;}p[1050],circle;double rad;int n,ans;double dist(double x1,double y1, double x2,double y2){	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));	}bool multi(point a,point b){	if((a.x-circle.x)*(b.y-circle.y)-(a.y-circle.y)*(b.x-circle.x)>=0)	return true;	return false;}void slove(){	int tmp;	for(int i=0;i<n;i++){		tmp=0;		for(int j=0;j<n;j++){			if(multi(p[i],p[j])){				tmp++;			}		}		if(tmp>ans) ans=tmp;	}}int main(){	int ni; double x,y;	while(scanf("%lf%lf%lf",&circle.x,&circle.y,&rad)!=EOF){		if(rad<0) break;		scanf("%d",&ni); n=0;		for(int i=0;i<ni;i++){			scanf("%lf%lf",&x,&y);			if(dist(x,y,circle.x,circle.y)<=rad){				p[n].x=x; p[n].y=y;				n++;			}		}	//	cout<<n<<endl;		if(rad==0) { printf("0\n"); continue; }		ans=0;		slove();		printf("%d\n",ans);	}	return 0;}