http://acm.sgu.ru/problem.php?contest=0&problem=435题目大意，每个UFO会使长草的地面变成荒地，使荒地长出草来，作用范围是一个圆，求最后荒地和草地面积各为多少。 圆的离散化，比赛的时候没有想仔细，没有做出来，赛后经haozi一点拨，发现可以做，就拿以前写的一个圆离散化的代码改了改，结果精度不够。重新写了一个，结果打错了一个变量，一直没有发现，WA到崩溃。
  sgu_435
1 #include<iostream>
2#include<complex>
3#include<cstring>
4#include<cstdio>
5#include<cmath>
6#include<algorithm>
7#include<vector>
8using namespace std;
9
10const int maxn = 120;
11//const double pi = acos( -1.0 );
12const double eps = 1e-8;
13struct point
14 {
15 double x, y;
16  point( ) { }
17 point( double _x, double _y ) : x( _x ), y( _y ) { }
18 };
19
20struct circle
21{
22 point p;
23 double r;
24 circle( ){ }
25 circle( point _p, double _r ) : p( _p ), r( _r ) { }
26};
27
28struct node
29{
30 double area;
31 int flag; // 标记圆弧是朝上还是朝下
32 double y, y1, y2;
33};
34
35circle c[maxn];
36vector<double> vec;
37double ans1, ans2;
38
39//计算 ab 和 ac 的叉积
40double det(const point& a, const point& b, const point& c){
41 return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
42}
43
44//计算 ab 和 ac 的点积
45double dot(point a,point b,point c){
46 return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
47}
48
49double fix(double x){return x < -1 ? -1 : ( x > 1 ? 1 : x ); }
50
51double dis(const point &a, const point &b){
52 return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
53}
54
55double dis2(const point &a, const point &b){
56 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
57}
58
59int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
60
61//求直线ab和直线cd的交点
62point cross(const point &a, const point &b, const point &c, const point &d)
63{
64 point ret = a;
65 double t = ( ( c.x - a.x ) * ( d.y - c.y ) - ( c.y - a.y ) * ( d.x - c.x ) ) /
66 ( ( b.x - a.x ) * ( d.y - c.y ) - ( b.y - a.y ) * ( d.x - c.x ) );
67 ret.x += ( b.x - a.x ) * t;
68 ret.y += ( b.y - a.y ) * t;
69 return ret;
70}
71
72//计算直线与圆的交点,保证直线与圆有交点
73void cross( const circle & b, const point &l1, const point &l2, point& p1, point& p2 )
74{
75 point p = b.p;
76 double t;
77 p.x += l1.y - l2.y;
78 p.y += l2.x - l1.x;
79 p = cross( p, b.p, l1, l2 );
80 double tem = b.r * b.r - ( p.x - b.p.x ) * ( p.x - b.p.x )
81 - ( p.y - b.p.y ) * ( p.y - b.p.y );
82 if( tem < 0 ) tem = 0;
83 t = sqrt( tem ) / dis( l1, l2 );
84 p2.x = p.x + ( l2.x - l1.x ) * t;
85 p2.y = p.y + ( l2.y - l1.y ) * t;
86 p1.x = p.x - ( l2.x - l1.x ) * t;
87 p1.y = p.y - ( l2.y - l1.y ) * t;
88}
89
90//计算圆与圆的交点,保证圆与圆有交点,圆心不重合
91
92void cross(const circle & a,const circle & b, point& p1, point& p2)
93{
94 point u, v;
95 double t = ( 1 + ( a.r * a.r - b.r * b.r ) / dis2( a.p, b.p ) ) / 2;
96 u.x = a.p.x + ( b.p.x - a.p.x ) * t;
97 u.y = a.p.y + ( b.p.y - a.p.y ) * t;
98 v.x = u.x + a.p.y - b.p.y;
99 v.y = u.y - a.p.x + b.p.x;
100 cross( a, u, v, p1, p2 );
101}
102
103
104bool cmp( const node & a, const node & b )
105{
106 return a.y > b.y;
107}
108
109void solve( double x1, double x2, const int & n )
110{
111 point p1, p2;
112 double x = ( x1 + x2 ) / 2, t;
113 vector<node> V;
114 node up, down; // up 朝下， down 朝上
115 for( int i = 1; i <= n; i++ )
116 {
117 if( dblcmp( c[i].p.x - c[i].r - x2 ) >= 0 )continue;
118 if( dblcmp( c[i].p.x + c[i].r - x1 ) <= 0 )continue;
119
120 up.flag = 2; down.flag = 1;
121
122 cross( c[i], point( x1, 0 ), point( x1, 1 ), p1, p2 );
123 if( p1.y > p2.y ) swap( p1, p2 );
124 up.y1 = p2.y, down.y1 = p1.y;
125
126 cross( c[i], point( x2, 0 ), point( x2, 1 ), p1, p2 );
127 if( p1.y > p2.y ) swap( p1, p2 );
128 up.y2 = p2.y, down.y2 = p1.y;
129
130 // y
131 cross( c[i], point( x, 0 ), point( x, 1 ), p1, p2 );
132 if( p1.y > p2.y ) swap( p1, p2 );
133 up.y = p2.y, down.y = p1.y;
134
135 p1 = point( x1, up.y1 ), p2 = point( x2, up.y2 );
136 t = acos( fix( dot( c[i].p, p1, p2 ) / c[i].r / c[i].r ) );
137 up.area = down.area = c[i].r * c[i].r * ( t - sin( t ) ) * 0.5;
138 V.push_back( up );
139 V.push_back( down );
140 }
141
142 sort( V.begin( ), V.end( ), cmp );
143 int cnt = 0;
144 for( int i = 0; i < V.size( ); i++)
145 {
146 double tem = 0;
147 if( V[i].flag == 1 )
148 {
149 cnt--;
150 tem -= V[i].area;
151 }
152 else
153 {
154 cnt++;
155 tem += V[i].area;
156 }
157 if( cnt > 0 )
158 {
159 if( V[i+1].flag == 1 ) tem += V[i+1].area;
160 else tem -= V[i+1].area;
161 tem += 0.5 * ( V[i].y1 - V[i+1].y1 + V[i].y2 - V[i+1].y2 ) * ( x2 - x1 );
162 if( cnt % 2 ) ans1 += tem;
163 else ans2 += tem;
164 }
165 }
166}
167
168void lisanhua( int n )
169{
170 point p1, p2;
171 vec.clear( );
172 for( int i = 1; i <= n; i++ )
173 {
174 vec.push_back( c[i].p.x + c[i].r );
175 vec.push_back( c[i].p.x - c[i].r );
176 }
177 for( int i = 1; i <= n; i++ )
178 {
179 for( int j = i + 1; j <= n; j++ )
180 {
181 double d = dis( c[i].p, c[j].p );
182 //if( samecircle( c[i], c[j] ) )continue;
183 if( dblcmp( c[i].r + c[j].r - d ) < 0 ||
184 dblcmp( fabs( c[i].r - c[j].r ) - d ) > 0 )continue;
185 cross( c[i], c[j], p1, p2 );
186 vec.push_back( p1.x );
187 vec.push_back( p2.x );
188 }
189 }
190 sort( vec.begin( ), vec.end( ) );
191 ans1 = ans2 = 0;
192 for( int i = 1; i < vec.size( ); i++ )
193 {
194 if( dblcmp( vec[i] - vec[i-1] ) == 0 )continue;
195 solve( vec[i-1], vec[i], n );
196 }
197 printf("%.5lf %.5lf\n",ans1, ans2);
198 //myunique( vec );
199}
200
201int main( )
202{
203 int n;
204 //freopen("in.in","r",stdin);
205 //freopen("out.txt","w",stdout);
206 while( scanf("%d",&n) != EOF )
207 {
208 for( int i = 1; i <= n; i++ )
209 scanf("%lf %lf %lf",&c[i].p.x,&c[i].p.y,&c[i].r);
210 lisanhua( n );
211 }
212 return 0;
213}
214
|