http://124.205.79.250/JudgeOnline/problem?id=1418 最近跟著haozi大牛學(xué)習(xí)計(jì)算幾何，第一道圓的離散化的題目。
題目的大致意思是按照時(shí)間順序把許多圓放在平面上，后放的圓可能將先放的圓覆蓋掉，最后求露出一部分的圓的個(gè)數(shù)。
用圓的左右極點(diǎn) 和 圓之間的交點(diǎn)將圓離散化，將x坐標(biāo)排序之后，從左往右掃描一下，對(duì)于每個(gè)區(qū)間用vis[ ]數(shù)組統(tǒng)計(jì)一下哪些圓沒(méi)被完全覆蓋。最后遍歷一下vis[ ]數(shù)組，計(jì)算出個(gè)數(shù)。
pku 1418
1
#include <cstdio>
2#include <iostream>
3#include <cmath>
4#include <complex>
5#include <algorithm>
6#include <cstring>
7#include <queue>
8#include <set>
9using namespace std;
10typedef complex<double> point;
11
12const int maxn = 103;
13const double eps = 1e-13;
14const double inf = 1e100;
15
16struct node
17
{
18
double y;
19 int id, flag;
20 bool operator<( const node & a )const
21
{
22 return y < a.y;
23
}
24
};
25
26struct circle
27{
28 point p;
29 double r;
30 circle( ){ }
31 circle( point u, double x ) : p( u ), r( x ){ }
32};
33circle c[maxn];
34vector<double> vec;
35int vis[maxn];
36
37double operator ^ ( const point p1, const point p2 ) { return imag( conj( p1 ) * p2 ); }
38double operator & ( const point p1, const point p2 ) { return real( conj( p1 ) * p2 ); }
39int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
40
41void intersect_circle_circle( circle c1, circle c2, point & p1, point & p2 )
42{
43 double d = abs( c1.p - c2.p );
44 double s = c1.r * c1.r + d * d - c2.r * c2.r;
45 double t = c2.r * c2.r + d * d - c1.r * c1.r;
46 point p = c1.p + ( c2.p - c1.p ) * s / ( s + t );
47 point p0( imag(c2.p) - imag(c1.p), real(c1.p) - real(c2.p) );
48 double d1 = abs( p - c1.p );
49 double l = abs( p0 );
50 double m = sqrt( c1.r * c1.r - d1 * d1 ) / l;
51 p1 = p + p0 * m;
52 p2 = p - p0 * m;
53}
54
55void lisanhua( int n )
56{
57 vec.clear( );
58 point p1, p2;
59 for( int i = 1; i <= n; i++ )
60 {
61 vec.push_back( real( c[i].p ) + c[i].r );
62 vec.push_back( real( c[i].p ) - c[i].r );
63 }
64 for( int i = 1; i <= n; i++ )
65 {
66 for( int j = i + 1; j <= n; j++ )
67 {
68 double t = fabs( c[i].r - c[j].r );
69 if( dblcmp( c[i].r + c[j].r - abs( c[i].p - c[j].p ) ) < 0 ||
70 dblcmp( t - abs( c[i].p - c[j].p ) ) > 0 )continue;
71 intersect_circle_circle( c[i], c[j], p1, p2 );
72 vec.push_back( real( p1 ) );
73 vec.push_back( real( p2 ) );
74 }
75 }
76 sort( vec.begin( ), vec.end( ) );
77}
78
79void solve( double x, int n )
80{
81 vector<node> V;
82 node tmp;
83 set<int> ID;
84 for( int i = 1; i <= n; i++ )
85 {
86 if( dblcmp( fabs( real( c[i].p ) - x ) - c[i].r ) > 0 )
87 continue;
88 double d = sqrt( c[i].r * c[i].r -
89 ( real( c[i].p ) - x ) * ( real( c[i].p ) - x ) );
90 tmp.y = imag( c[i].p ) - d;
91 tmp.id = -i;
92 tmp.flag = 0;
93 V.push_back( tmp );
94 tmp.y = imag( c[i].p ) + d;
95 //tmp.id = i;
96 tmp.flag = 1;
97 V.push_back( tmp );
98 }
99 sort( V.begin( ), V.end( ) );
100 for( int i = 0; i < V.size( ); i++ )
101 {
102 if( ID.size( ) != 0 ) vis[-(*ID.begin())] = 1;
103 if( V[i].flag == 0 ) ID.insert( V[i].id );
104 else ID.erase( V[i].id );
105 if( ID.size( ) != 0 ) vis[-(*ID.begin())] = 1;
106 }
107}
108
109int main(int argc, char *argv[])
110{
111 int n;
112 double x, y, r;
113 while( scanf("%d",&n) && n )
114 {
115 for( int i = 1; i <= n; i++ )
116 {
117 scanf("%lf%lf%lf",&x,&y,&r);
118 c[i] = circle( point( x, y ), r );
119 }
120 lisanhua( n );
121 memset( vis, 0, sizeof( vis ) );
122 for( int i = 1; i < vec.size( ); i++ )
123 {
124 if( dblcmp( vec[i] - vec[i-1] ) == 0 )continue;
125 solve( ( vec[i] + vec[i-1] ) / 2, n );
126 }
127 int ans = 0;
128 for( int i = 1; i <= n; i++ )
129 if( vis[i] )ans++;
130 printf("%d\n",ans);
131 }
132 return 0;
133}
134