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 |
求DaLao指点,贴代码#include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> using namespace std; const int Max=1010; struct dao { double st; double ed; }b[Max]; bool f[Max]; void Qsort(int l,int r) { int i,j; dao x,temp; i=l; j=r; x=b[(l+r)/2]; while(i<=j) { while(x.ed>b[i].ed||(x.ed==b[i].ed&&x.st>b[i].st)) i++; while(x.ed<b[j].ed||(x.ed==b[j].ed&&x.st<b[j].st)) j--; if(i<=j) { temp=b[i]; b[i]=b[j]; b[j]=temp; i++; j--; } } if(i<r) Qsort(i,r); if(l<j) Qsort(l,j); } int main() { int n,d; double x,y; int res=0; double s; bool fff=false; int iii=0; while(1) { iii++; scanf("%d%d",&n,&d); if(!n&&!d) break; for(int i=1; i<=n; i++) { scanf("%lf%lf",&x,&y); if(y>d) fff=true; b[i].st=x-sqrt(d*d-y*y); b[i].ed=x+sqrt(d*d-y*y); f[i]=false; } if(fff) { printf("Case %d: -1\n",iii); break; } Qsort(1,n); res=0; for(int i=1; i<=n; i++) { if(!f[i]) { f[i]=true; res++; for(int j=i+1; j<=n; j++) if(!f[j]&&b[j].st<=b[i].ed) f[j]=true; } } printf("Case %d: %d\n",iii,res); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator