• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
50%
SHARE
TWEET

# Untitled

a guest Aug 12th, 2017 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cstdio>
2. #include <cmath>
3. #include <algorithm>
4. #include <ctype.h>
5. #include <vector>
6.
7. using namespace std;
8. const double EPS = 1e-9;
9.
10. inline bool lt( double a, double b ) {
11.     return a + EPS < b;
12. }
13.
14. inline bool gt( double a, double b ) {
15.     return lt( b, a );
16. }
17.
18. inline bool eq( double a, double b ) {
19.     return !lt( a, b ) && !lt( b, a );
20. }
21.
22. inline bool lte( double a, double b ) {
23.     return !gt( a, b );
24. }
25.
26. inline bool gte( double a, double b ) {
27.     return !lt( a, b );
28. }
29.
30. struct tocka {
31.     double x, y;
32.     tocka( double x = 0, double y = 0 ) {
33.         this -> x = x;
34.         this -> y = y;
35.     }
36. };
37.
38. struct duzina {
39.     tocka A, B;
40.     duzina( const tocka& A, const tocka& B ) {
41.         this -> A = A;
42.         this -> B = B;
43.     }
44. };
45.
46. struct pravac {
47.     double a, b, c;
48.     pravac( void ){}
49.     pravac( double a, double b, double c ) {
50.         this -> a = a;
51.         this -> b = b;
52.         this -> c = c;
53.     }
54.     pravac( const tocka& P, const tocka& Q ) {
55.         a = P.y - Q.y;
56.         b = Q.x - P.x;
57.         c = a * P.x + b * P.y;
58.     }
59.     pravac( const duzina& D ) {
60.         *this = pravac( D.A, D.B );
61.     }
62. };
63.
64. int predznak( double x ) {
65.     if( lt( x, 0 ) ) return -1;
66.     if( gt( x, 0 ) ) return 1;
67.     return 0;
68. }
69.
70. int ccw( const tocka& A, const tocka& B, const tocka& C ) {
71.     double p = ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
72.     return predznak( p );
73. }
74.
75. double udaljenost( const tocka& A, const tocka& B ) {
76.     return sqrt( pow( A.x - B.x, 2 ) + pow( A.y - B.y, 2 ) );
77. }
78.
79. double udaljenost( const tocka& T, const pravac& P ) {
80.     return ( P.a * T.x + P.b * T.y - P.c ) / sqrt( P.a * P.a + P.b * P.b );
81. }
82.
83. double udaljenost( const tocka& T, const duzina& D ) {
84.     double a = udaljenost( D.B, T );
85.     double b = udaljenost( D.A, T );
86.     double c = udaljenost( D.A, D.B );
87.     if( gt( b * b, a * a + c * c ) ) return a;
88.     if( gt( a * a, b * b + c * c ) ) return b;
89.     return udaljenost( T, pravac( D ) );
90. }
91.
92. bool sijeku( const pravac &P, const tocka &T ) {
93.     return eq( P.a * T.x + P.b * T.y, P.c );
94. }
95.
96. bool sijeku( const duzina &D, const tocka &T ) {
97.     return eq( udaljenost( T, D ), 0 );
98. }
99.
100. bool sijeku( const pravac &P1, const pravac &P2 ) { // ne radi za p1 = p2
101.     return !eq( P1.a * P2.b - P2.a * P1.b, 0 );
102. }
103.
104. bool sijeku( const pravac &P, const duzina &D ) {
105.     int p1 = predznak( P.a * D.A.x + P.b * D.A.y - P.c );
106.     int p2 = predznak( P.a * D.B.x + P.b * D.B.y - P.c );
107.     return p1 * p2 <= 0;
108. }
109.
110. bool sijeku( const duzina& D1, const duzina& D2 ) {
111.     if( sijeku( pravac( D1 ), D2.A ) && sijeku( pravac( D1 ), D2.B ) )
112.         return sijeku( D1, D2.A ) || sijeku( D1, D2.B ) || sijeku( D2, D1.A ) || sijeku( D2, D1.B );
113.     else
114.         return sijeku( pravac( D1 ), D2 ) && sijeku( pravac( D2 ), D1 );
115. }
116.
117. tocka poloviste( const tocka& A, const tocka& B ) {
118.     return tocka( ( A.x + B.x ) / 2, ( A.y + B.y ) / 2 );
119. }
120.
121. pravac okomica( const pravac& P, const tocka& T ) {
122.     return pravac( P.b, - P.a, P.b * T.x - P.a * T.y );
123. }
124.
125. tocka sjeciste( const pravac& P1, const pravac& P2 ) {
126.     double x = ( P1.c * P2.a - P1.a * P2.c ) / ( P1.a * P2.b - P1.b * P2.a );
127.     double y = ( P1.b * P2.c - P1.c * P2.b ) / ( P2.a * P2.b - P1.b * P2.a );
129. }
130.
131. tocka sjeciste( const pravac& P, const duzina& D ) {
132.     return sjeciste( P, pravac( D ) );
133. }
134.
135. struct kruznica {
136.     tocka S;
137.     double r;
138.     kruznica( const tocka& S, const double& r ) {
139.         this -> S = S; this -> r = r;
140.     }
141.     kruznica( const tocka& A, const tocka& B, const tocka& C ) {
142.         S = sjeciste( okomica( pravac( A, B ), poloviste( A, B ) ), okomica( pravac( B, C ), poloviste( B, C ) ) );
143.     }
144. };
145.
146. bool sijeku( const kruznica& K, const pravac &P ) {
147.     return lt( udaljenost( K.S, P ), K.r );
148. }
149.
150. bool sijeku( const kruznica& K1, const kruznica& K2 ) {
151.     double d = udaljenost( K1.S, K2.S );
152.     if ( gt( d, K1.r + K2.r ) ) return 0;
153.     if ( lt( d, abs( K1.r - K2.r ) ) ) return 0;
154.     return 1;
155. }
156.
157.
158.
159. const int MXN = 110;
160. int N, K;
161. double niz[MXN][ 3 ];
162. pravac pravci[ MXN ];
163. vector <tocka> tocke;
164.
165.
166. void ucitaj( double &t ){
167.     char a = ' ';
168.     while( !isdigit( a = getchar() ) );
169.     t = 0.0;
170.     do{
171.         t *= 10.0;
172.         t += a - '0';
173.     }while( isdigit( a = getchar() ) );
174. }
175.
176.
177. int main(){
178.     scanf( "%d", &N );
179.     for( int i = 0; i < N; i++ ){
180.         scanf( "%lf", &niz[ i ][ 0 ] );
181.         scanf( "%lf", &niz[ i ][ 1 ] );
182.         scanf( "%lf", &niz[ i ][ 2 ] );
183.         niz[ i ][ 0 ] = 1.0 / niz[ i ][ 0 ];
184.         niz[ i ][ 1 ] = 1.0 / niz[ i ][ 1 ];
185.         niz[ i ][ 2 ] = 1.0 / niz[ i ][ 2 ];
186.     }
187.     tocka t;
188.     for( int i = 0 ; i < N ; ++i ){
190.         for( int j = 0 ; j < N ; ++j ){
191.             if( i == j ) continue;
192.            pravci[ cookie ] = pravac( niz[ j ][ 0 ] - niz[ i ][ 0 ],  niz[ j ][ 1 ] - niz[ i ][ 1 ],  niz[ j ][ 2 ] - niz[ i ][ 2 ] );
194.         }
196.         tocke.clear();
197.         for( int j = 0 ; j < N ; ++j ){
198.             for( int k = 0 ; k < N ; ++k ){
199.                 t = sjeciste( pravci[ j ], pravci[ k ] );
200.                 tocke.push_back( t );
201.             }
202.         }
203.         for( int j = 0 ; j < N ; ++j ){
204.             for( int k = 0 ; k < tocke.size() ;  ){
205.                 if( gt( udaljenost( tocke[ k ], pravci[ j ] ), 0.0 ) ){
206.                     swap( tocke[ k ], tocke.back() );
207.                     tocke.pop_back();
208.                 } else {
209.                     ++k;
210.                 }
211.             }
212.         }
214.         double tr, drugi;
215.         for( int j = 0 ; j < tocke.size() ; ++j ){
216.             bool tmp = true;
217.             for( int k = 0 ; k < N ; ++k ){
218.                 if( j == k ) continue;
219.                 tr = tocke[ j ].x * niz[ i ][ 0 ];
220.                 tr += tocke[ j ].y * niz[ i ][ 1 ];
221.                 tr += niz[ i ][ 2 ];
222.                 drugi = tocke[ j ].x * niz[ k ][ 0 ];
223.                 drugi += tocke[ j ].y * niz[ k ][ 1 ];
224.                 drugi += niz[ k ][ 2 ];
225.                 if( ! lt( tr, drugi ) ){
226.                     tmp = false;
227.                     break;
228.                 }
229.             }