| ||||||||||
| 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了N次,能找到的测试数据都过了代码如下,帮忙看一下,用的贪心的思路
#include <iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<stdio.h>
using namespace std;
struct node
{
double head,tail;
}a[1005];
int cmp(const void *a,const void *b)
{
return (*(node *)a).tail>(*(node *)b).tail?1:-1;
}
int main()
{
//freopen("in.txt","r",stdin);
int n,d;
char s[100];
int c=1;
while(cin>>n>>d,n||d)
{
memset(a,0,sizeof(a));
int num=1;
int i;
int x,y;
int flag=0;
double temp;
for(i=0;i<n;i++)
{
cin>>x>>y;
if(y>d||d<0) flag=1;
temp=sqrt((double)d*d-y*y);
a[i].head=(double)x-temp;
a[i].tail=(double)x+temp;
}
gets(s);
if(flag)
{
cout<<"Case "<<c<<": "<<"-1"<<endl;
c++;
continue;
}
qsort(a,n,sizeof(node),cmp);
int h=a[0].head,t=a[0].tail;
for(i=1;i<n;i++)
{
if(a[i].head<=t)
{
if(a[i].tail<t)
{
h=a[i].head;
t=a[i].tail;
}
}
else
{
h=a[i].head;
t=a[i].tail;
num++;
}
}
cout<<"Case "<<c<<": "<<num<<endl;
c++;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator