poj 1819 Disks

 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\n",num);
58         for(int i=1; i<=n; i++)
59         {
60             if(flag[i])
61             {
62                 printf("%d\n",i);
63             }
64         }
65     }
66     return 0;
67 }