http://poj.org/problem?id=1819
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 8 const double eps=1e-8; 9 struct point 10 { 11 double x; 12 double y,r; 13 }pp[2000]; 14 bool flag[2000]; 15 int stack1[2000],n; 16 17 int main() 18 { 19 while(scanf("%d",&n)!=EOF) 20 { 21 double x; 22 int p=0,i,last; 23 for(last=i=1; i<=n; i++){ 24 flag[i]=true; 25 scanf("%lf",&pp[i].r); 26 int k=0; 27 pp[i].x=pp[i].y=pp[i].r; 28 for(int j=1; j<=p; j++) 29 { 30 x=pp[stack1[j]].x+2*sqrt(pp[i].r*pp[stack1[j]].r); 31 if(x-pp[i].x>eps) 32 { 33 pp[i].x=x; 34 k=j; 35 } 36 } 37 p=k; 38 stack1[++p]=i; 39 if(pp[i].x+pp[i].r-pp[last].x-pp[last].r>eps) 40 { 41 last=i; 42 } 43 } 44 for(int i=1; i<=p; i++) flag[stack1[i]]=0; 45 for(int j=last+1; j<=n; j++) 46 { 47 flag[j]=true; 48 } 49 int num=0; 50 for(int i=1; i<=n; i++) 51 { 52 if(flag[i]) 53 { 54 num++; 55 } 56 } 57 printf("%d ",num); 58 for(int i=1; i<=n; i++) 59 { 60 if(flag[i]) 61 { 62 printf("%d ",i); 63 } 64 } 65 } 66 return 0; 67 }