Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我用向量做的,怎么还是WA,又什么恶心数据吗?谢谢

Posted by trueshlqsh at 2007-10-19 19:52:50 on Problem 1106
我的方法是:先用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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator