Posted on 2009-09-17 20:36
Uriel 阅读(340)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
计算几何
最近一直在搞计算几何。。不过不是钻研。。而是临时抱佛脚应付比赛。。。- -||
判断给定圆心，半径的半圆最多覆盖多少点。。
叉积应用---叉积正负判断夹角是否180度以内。。
/**//*Problem: 1106 User: Uriel
Memory: 176K Time: 0MS
Language: C++ Result: Accepted*/
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define MAXN 1001
typedef struct point
{
int x,y;
};
point P[MAXN],a,t;
int MAX;
double r;
int cross_product(point a,point c,point b)
{
return (a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y);
}
int In_Circle(point a,point b,double r)
{
if((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<=r*r)
{
return 1;
}
return 0;
}
int main()
{
int i,j,k,n;
while(scanf("%d %d %lf",&a.x,&a.y,&r)!=EOF)
{
if(r<0)break;
scanf("%d",&n);
k=0;
for(i=1;i<=n;i++)
{
scanf("%d %d",&t.x,&t.y);
if(In_Circle(a,t,r))
{
P[++k].x=t.x;
P[k].y=t.y;
}
}
MAX=0;
for(i=1;i<=k;i++)
{
int temp=0;
for(j=1;j<=k;j++)
{
if(cross_product(P[i],a,P[j])<=0)
{
temp++;
}
}
if(2*temp<k) //看Discuss才想到的
{
temp=k-temp;
}
if(temp>MAX)MAX=temp;
}
printf("%d\n",MAX);
}
system("PAUSE");
return 0;
}