| ||||||||||
| 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啊!是不是算法错误了!
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator