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