圓的離散化。
這道題是依次往墻上涂圓，后涂的會覆蓋前涂的。統(tǒng)計(jì)有多少圓能看見。
取所有圓的左右極點(diǎn)，交點(diǎn)的x軸坐標(biāo)離散，這樣每一個單位豎條要么和圓不相交，要么被圓跨立（或相切），然后每個豎條完全可以抽象成矩形
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, false, sizeof(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 閱讀(304)
評論(0) 編輯 收藏 引用 所屬分類:
geometry