poj 1819

题目链接：https://vjudge.net/problem/POJ-1819

题意：给你一些圆，问你水平排序后可以删除哪些圆不影响。

我们可以这样，从左往右枚举 c[i] 圆，然后从小于 i 的 园中找与其相切的相对应横坐标x，取个max，然后就得到坐标，两坐标间的圆可删去。注意特判最左和最右。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int N = 1e3+9;
 6 struct Circle{
 7     double x,y,r;
 8 }p[N];
 9 int vis[N];
10 double cir_cir(Circle c,double lr){
11     double d = sqrt( (c.r+lr)*(c.r+lr) - (c.r-lr)*(c.r-lr));
12     return c.x + d;
13 }
14 int main(){
15     int n; scanf("%d",&n);
16     for(int i = 1; i <= n;++i) scanf("%lf",&p[i].r);
17     p[1].x = p[1].y = p[1].r;
18     for(int i = 2;i<=n;++i){
19         double maxx = -1;
20         int le;
21         for(int j = i-1 ; j>=1;--j){
22             double temx = cir_cir(p[j],p[i].r);
23             if(temx > maxx){
24                 maxx = temx;
25                 le = j;
26             }
27         }
28         p[i].x = maxx; p[i].y = p[i].r;
29         for(int u = i-1;u>le;--u) vis[u] = 1;
30     }
31     for(int i = 2;i<=n;++i){
32         if(p[i].x <= p[i].r ){
33             for(int j = 1;j<i;++j) vis[j] = 1;
34         }
35     }
36     double ri = p[n].x + p[n].r;
37     for(int i = 1;i<n;++i){
38         if( ri - p[i].x <= p[i].r ){
39             for(int j = i+1;j<=n;++j) vis[j] = 1;
40         }
41     }
42     int tot = 0;
43     for(int i = 1;i<=n;++i){
44         // cerr<<i<<' '<<vis[i]<<endl;
45         tot+=vis[i];
46     }
47     printf("%d\n",tot);
48     for(int i = 1;i<=n;++i) if(vis[i]) printf("%d\n",i);
49     return 0;
50 }

View Code