随笔-21  评论-10  文章-21  trackbacks-0
圆的离散化。
这道题是依次往墙上涂圆,后涂的会覆盖前涂的。统计有多少圆能看见。
取所有圆的左右极点,交点的x轴坐标离散,这样每一个单位竖条要么和圆不相交,要么被圆跨立(或相切),然后每个竖条完全可以抽象成矩形

  1 #include<iostream>
  2 #include<cstring>
  3 #include<set>
  4 #include<vector>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 #define eps 1e-13
 10 struct point{double x,y;};
 11 struct node{
 12     double y; int id, flag;
 13     bool operator<(const node & a)const
 14     {
 15         return y < a.y;
 16     }
 17 };
 18 
 19 int dcmp( double x){return x < -eps ? -1 : x > eps; }
 20 
 21 double Dis(point p1,point p2){
 22     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
 23 }
 24 
 25 point intersection(point u1,point u2,point v1,point v2){
 26     point ret=u1;
 27     double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
 28             /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
 29     ret.x+=(u2.x-u1.x)*t;
 30     ret.y+=(u2.y-u1.y)*t;
 31     return ret;
 32 }
 33 
 34 void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2){
 35     point p=c;
 36     double t;
 37     p.x+=l1.y-l2.y;
 38     p.y+=l2.x-l1.x;
 39     p=intersection(p,c,l1,l2);
 40     t=sqrt(r*r-Dis(p,c)*Dis(p,c))/Dis(l1,l2);
 41     p1.x=p.x+(l2.x-l1.x)*t;
 42     p1.y=p.y+(l2.y-l1.y)*t;
 43     p2.x=p.x-(l2.x-l1.x)*t;
 44     p2.y=p.y-(l2.y-l1.y)*t;
 45 }
 46 
 47 void intersection_circle_circle(point c1,double r1,point c2,double r2,point& p1,point& p2){
 48     point u,v;
 49     double t;
 50     t=(1+(r1*r1-r2*r2)/Dis(c1,c2)/Dis(c1,c2))/2;
 51     u.x=c1.x+(c2.x-c1.x)*t;
 52     u.y=c1.y+(c2.y-c1.y)*t;
 53     v.x=u.x+c1.y-c2.y;
 54     v.y=u.y-c1.x+c2.x;
 55     intersection_line_circle(c1,r1,u,v,p1,p2);
 56 }
 57 
 58 
 59 
 60 int n;
 61 point p[128];
 62 double r[128];
 63 bool view[128];
 64 vector<double> distinc;
 65 
 66 void get_distinc(){
 67     distinc.clear();
 68     for(int i = 0 ; i < n; i++)
 69     {
 70         distinc.push_back(p[i].x + r[i]);
 71         distinc.push_back(p[i].x - r[i]);
 72     }
 73     point p1, p2;
 74     for(int i = 0 ; i < n; i++)
 75         for(int j = i+1; j < n; j++)
 76             if( Dis(p[i], p[j]) <= r[i] + r[j] ){
 77                 intersection_circle_circle(p[i], r[i], p[j], r[j], p1, p2);
 78                 distinc.push_back(p1.x);
 79                 distinc.push_back(p2.x);
 80             }
 81    sort(distinc.begin(), distinc.end() );
 82 }
 83 
 84 
 85 
 86 
 87 void gao(double xx){
 88     set<int> ID;
 89     vector<node> C;
 90     node tem;
 91     for(int i = 0; i < n; i++)
 92     {
 93         if( fabs(p[i].x - xx) > r[i] )continue;
 94         double d = sqrt( r[i]*r[i] - (p[i].x - xx)*(p[i].x - xx) );
 95         tem.id = -i;
 96         tem.y = p[i].y - d;
 97         tem.flag = 0;
 98         C.push_back(tem);
 99         tem.y = p[i].y + d;
100         tem.flag = 1;
101         C.push_back(tem);
102     }
103     sort(C.begin(), C.end() );
104     for(int i = 0; i < C.size(); i++){
105         if(ID.size() != 0)view[ -*ID.begin() ) ] = true;
106         if(C[i].flag==0)ID.insert(C[i].id); else ID.erase(C[i].id);
107         if(ID.size() != 0)view[ -*ID.begin() ) ] = true;
108     }
109 }
110 
111 int main(){
112     //freopen("in","r",stdin);
113     while(scanf("%d"& n)!=EOF && n){
114         for(int i = 0; i < n; i++)
115             scanf("%lf %lf %lf",&p[i].x, &p[i].y, &r[i]);
116         memset(view, falsesizeof(view) );
117         get_distinc();
118         for(int i = 1; i < distinc.size(); i++){
119             if( dcmp(distinc[i-1- distinc[i])==0)continue;
120             gao( (distinc[i-1+ distinc[i])/2 );
121         }
122         int ans = 0;
123         for(int i = 0; i < n; i++)ans += view[i];
124         printf("%d\n",ans);
125     }
126 }


posted on 2009-11-02 21:38 wangzhihao 阅读(259) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理