| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我用向量做的,怎么还是WA,又什么恶心数据吗?谢谢我的方法是:先用SQRT运算把在圆内的点统计出来,然后一个点一个点地和圆心连线判断,用向量做,统计左边和右边地点个数,替换ANS
//From:PKU 1106
//Time:Oct. 19th
#include <iostream>
#include <cmath>
using namespace std;
long x,y;
double r;
long ans;
long n,len;
long data[200][3];
long in_c[200];
int main()
{
long i,xp,yp,left,right,j;
while (cin>>x>>y>>r)
{
if (r<0) break;
//init;
cin>>n;
for (i=1;i<=n;i++) cin>>data[i][1]>>data[i][2];
len=0;
for (i=1;i<=n;i++)
if (r-sqrt((x-data[i][1])*(x-data[i][1])+(y-data[i][2])*(y-data[i][2]))>=0.00001)
{
len++;
in_c[len]=i;
}
//main;
ans=0;
for (i=1;i<=len;i++)
{
xp=data[in_c[i]][1]-x;
yp=data[in_c[i]][2]-y;
left=0;
right=0;
for (j=1;j<=len;j++)
if (-yp*(data[in_c[j]][1]-x)+xp*(data[in_c[j]][2]-y)>0) left++;
else if (-yp*(data[in_c[j]][1]-x)+xp*(data[in_c[j]][2]-y)<0) right++;
else {left++;right++;}
if (left>ans) ans=left;
if (right>ans) ans=right;
}
//print;
cout<<ans<<endl;
}
// system("pause");
return 0;
}
谢谢
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator