Posted on 2009-09-17 20:36
Uriel 閱讀(366)
評論(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;
}