SHARE
TWEET

Untitled

a guest Aug 12th, 2017 39 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 );
  128.     return tocka( x, y );
  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 ){
  189.         int cookie = 0;
  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 ] );
  193.            cookie++;
  194.         }
  195.         cookie = 0;
  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.         }
  213.         bool answer= false;
  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.             }
  230.             answer |= tmp;
  231.         }
  232.         printf( "%d %d %s\n", i, tocke.size(), answer ? "Yes" : "No" );
  233.     }
  234.     return 0;
  235. }
RAW Paste Data
Top