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

Re:大家看看我的算法哪里错了,提了N次都是wrong answer

Posted by liumingod at 2005-09-27 12:59:05 on Problem 1106
In Reply To:大家看看我的算法哪里错了,提了N次都是wrong answer Posted by:liumingod at 2005-09-27 12:56:32
> 
> 先排除不在圆里的,也就是只储存在圆里的点。覆盖最多的半圆肯定是边界在一个点上面,于是就用一个点和圆心的直线作为方程,将每个点代进去算,大于等于零在左半边圆,小于等于零在右半边圆,然后在每一个点用以上算法循环。。统计最大值,这好象没地方错吧。。
忘了贴SC
#include "iostream.h"

int done()
{ int x[151];
  int y[151];
  int x1,y1;

  int n;
  int total;
  float r;
  while (true)
  {
  cin>>x[0]>>y[0]>>r;
 
  if (r<=0) return 0;
    else
	{ total=1;
	 
	   cin>>n;
	  for (int i=1;i<=n;i++)
	  { 
         cin>>x1>>y1;
	     x1=x1-x[0]; 
		 y1=y1-y[0];
		 if ((x1*x1+y1*y1)-r*r<=0)
		 { x[total]=x1;
		   y[total]=y1;
		   total++;
		 }
	  }
     total--;
	 
//	 float ks;
	 int maxtotal=1;

     for (i=1;i<=total;i++)
	 { int left_total=1;
	   int right_total=1;
		 if (x[i]==0)
		 { for (int j=1;j<=total;j++)
		
			 if (i!=j) 
			 { if  (x[j]<=0) left_total++;
			   if  (x[j]>=0) right_total++; 
			   
			 }
		 }
	  else
 
	 { // ks=((float)y[i])/((float)x[i]);

		 for (int j=1;j<=total;j++)
		 {
			 if (i!=j) 
			 { if  (y[i]*x[j]-x[i]*y[j]<=0) left_total++;
			   if  (y[i]*x[j]-x[i]*y[j]>=0) right_total++; 
			   
			 }

            
		 }
     }

         if (left_total>maxtotal) maxtotal=left_total;
	     if (right_total>maxtotal) maxtotal=right_total;
       
	 }

	 cout<<maxtotal<<"\n";
	}	
  }
  
  
}

int main(int argc, char* argv[])
{    done();
	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