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

大牛,帮帮小弟啊!急求。。。

Posted by cai at 2007-10-25 21:30:35 on Problem 1328
为什么老是WA啊!是不是算法错误了!
#include<iostream>
#include<cmath>
#include <cstdlib>
using namespace std;

struct node
{
     int x; 
	 int y;
}a[1000]; 

int ip = 0;
int n;

int cmp(const void *p1,const void *p2)
{
    node n1= *(struct node *) p1;
    node n2= *(struct node *) p2;
   return n1.x-n2.x;
}

bool  finep(int flag[])
{  
	int i;
	for (i=0; i<n; i++)
		if(flag[i] != 1){
			ip = i; 
               return true;
		}
		return false; 
}


int main()
{  
	int  d, fine=1, j=1;
	int flag[1000] ; 
	while (cin>>n>>d && n!=0 )
    {
		 d*=2;  
		fine = 1; 
          memset(flag, 0, sizeof(flag));
	      int i;        
          for (i=0; i<n; i++){
			  cin>>a[i].x>>a[i].y; 
			  
		  }
		  qsort(a, n, sizeof(a[0]), cmp);
		 // for(i=0; i<n; i++)
		//	  cout<<a[i].x<<' '<<a[i].y<<endl;
		  int result=0; 
		  while (finep(flag)){
			      result++; 
				  if (a[ip].y > d/2 || a[ip].y < 0){
				     fine = 0; 
				      break;
				  }
				 float xx = a[ip].x + sqrt(pow(d/2.0, 2.0)-pow(a[ip].y, 2.0)); 
				 flag[ip] = 1;
				 for (i=0; i<n && a[i].x<=xx+d/2; i++){
				      if (pow((a[i].x-xx)*1.0, 2.0) + pow(a[i].y*1.0, 2.0) <= pow(d/2.0, 2.0))
						  flag[i] = 1; 
				 
				 }
		  
		  }
	   if (fine == 0)
		   printf("Case %d: -1\n", j++);
	   else 
		   printf("Case %d: %d\n", j++, result);
	
	}

  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