Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- #include <ctype.h>
- #include <vector>
- using namespace std;
- const double EPS = 1e-9;
- inline bool lt( double a, double b ) {
- return a + EPS < b;
- }
- inline bool gt( double a, double b ) {
- return lt( b, a );
- }
- inline bool eq( double a, double b ) {
- return !lt( a, b ) && !lt( b, a );
- }
- inline bool lte( double a, double b ) {
- return !gt( a, b );
- }
- inline bool gte( double a, double b ) {
- return !lt( a, b );
- }
- struct tocka {
- double x, y;
- tocka( double x = 0, double y = 0 ) {
- this -> x = x;
- this -> y = y;
- }
- };
- struct duzina {
- tocka A, B;
- duzina( const tocka& A, const tocka& B ) {
- this -> A = A;
- this -> B = B;
- }
- };
- struct pravac {
- double a, b, c;
- pravac( void ){}
- pravac( double a, double b, double c ) {
- this -> a = a;
- this -> b = b;
- this -> c = c;
- }
- pravac( const tocka& P, const tocka& Q ) {
- a = P.y - Q.y;
- b = Q.x - P.x;
- c = a * P.x + b * P.y;
- }
- pravac( const duzina& D ) {
- *this = pravac( D.A, D.B );
- }
- };
- int predznak( double x ) {
- if( lt( x, 0 ) ) return -1;
- if( gt( x, 0 ) ) return 1;
- return 0;
- }
- int ccw( const tocka& A, const tocka& B, const tocka& C ) {
- double p = ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
- return predznak( p );
- }
- double udaljenost( const tocka& A, const tocka& B ) {
- return sqrt( pow( A.x - B.x, 2 ) + pow( A.y - B.y, 2 ) );
- }
- double udaljenost( const tocka& T, const pravac& P ) {
- return ( P.a * T.x + P.b * T.y - P.c ) / sqrt( P.a * P.a + P.b * P.b );
- }
- double udaljenost( const tocka& T, const duzina& D ) {
- double a = udaljenost( D.B, T );
- double b = udaljenost( D.A, T );
- double c = udaljenost( D.A, D.B );
- if( gt( b * b, a * a + c * c ) ) return a;
- if( gt( a * a, b * b + c * c ) ) return b;
- return udaljenost( T, pravac( D ) );
- }
- bool sijeku( const pravac &P, const tocka &T ) {
- return eq( P.a * T.x + P.b * T.y, P.c );
- }
- bool sijeku( const duzina &D, const tocka &T ) {
- return eq( udaljenost( T, D ), 0 );
- }
- bool sijeku( const pravac &P1, const pravac &P2 ) { // ne radi za p1 = p2
- return !eq( P1.a * P2.b - P2.a * P1.b, 0 );
- }
- bool sijeku( const pravac &P, const duzina &D ) {
- int p1 = predznak( P.a * D.A.x + P.b * D.A.y - P.c );
- int p2 = predznak( P.a * D.B.x + P.b * D.B.y - P.c );
- return p1 * p2 <= 0;
- }
- bool sijeku( const duzina& D1, const duzina& D2 ) {
- if( sijeku( pravac( D1 ), D2.A ) && sijeku( pravac( D1 ), D2.B ) )
- return sijeku( D1, D2.A ) || sijeku( D1, D2.B ) || sijeku( D2, D1.A ) || sijeku( D2, D1.B );
- else
- return sijeku( pravac( D1 ), D2 ) && sijeku( pravac( D2 ), D1 );
- }
- tocka poloviste( const tocka& A, const tocka& B ) {
- return tocka( ( A.x + B.x ) / 2, ( A.y + B.y ) / 2 );
- }
- pravac okomica( const pravac& P, const tocka& T ) {
- return pravac( P.b, - P.a, P.b * T.x - P.a * T.y );
- }
- tocka sjeciste( const pravac& P1, const pravac& P2 ) {
- double x = ( P1.c * P2.a - P1.a * P2.c ) / ( P1.a * P2.b - P1.b * P2.a );
- double y = ( P1.b * P2.c - P1.c * P2.b ) / ( P2.a * P2.b - P1.b * P2.a );
- return tocka( x, y );
- }
- tocka sjeciste( const pravac& P, const duzina& D ) {
- return sjeciste( P, pravac( D ) );
- }
- struct kruznica {
- tocka S;
- double r;
- kruznica( const tocka& S, const double& r ) {
- this -> S = S; this -> r = r;
- }
- kruznica( const tocka& A, const tocka& B, const tocka& C ) {
- S = sjeciste( okomica( pravac( A, B ), poloviste( A, B ) ), okomica( pravac( B, C ), poloviste( B, C ) ) );
- }
- };
- bool sijeku( const kruznica& K, const pravac &P ) {
- return lt( udaljenost( K.S, P ), K.r );
- }
- bool sijeku( const kruznica& K1, const kruznica& K2 ) {
- double d = udaljenost( K1.S, K2.S );
- if ( gt( d, K1.r + K2.r ) ) return 0;
- if ( lt( d, abs( K1.r - K2.r ) ) ) return 0;
- return 1;
- }
- const int MXN = 110;
- int N, K;
- double niz[MXN][ 3 ];
- pravac pravci[ MXN ];
- vector <tocka> tocke;
- void ucitaj( double &t ){
- char a = ' ';
- while( !isdigit( a = getchar() ) );
- t = 0.0;
- do{
- t *= 10.0;
- t += a - '0';
- }while( isdigit( a = getchar() ) );
- }
- int main(){
- scanf( "%d", &N );
- for( int i = 0; i < N; i++ ){
- scanf( "%lf", &niz[ i ][ 0 ] );
- scanf( "%lf", &niz[ i ][ 1 ] );
- scanf( "%lf", &niz[ i ][ 2 ] );
- niz[ i ][ 0 ] = 1.0 / niz[ i ][ 0 ];
- niz[ i ][ 1 ] = 1.0 / niz[ i ][ 1 ];
- niz[ i ][ 2 ] = 1.0 / niz[ i ][ 2 ];
- }
- tocka t;
- for( int i = 0 ; i < N ; ++i ){
- int cookie = 0;
- for( int j = 0 ; j < N ; ++j ){
- if( i == j ) continue;
- pravci[ cookie ] = pravac( niz[ j ][ 0 ] - niz[ i ][ 0 ], niz[ j ][ 1 ] - niz[ i ][ 1 ], niz[ j ][ 2 ] - niz[ i ][ 2 ] );
- cookie++;
- }
- cookie = 0;
- tocke.clear();
- for( int j = 0 ; j < N ; ++j ){
- for( int k = 0 ; k < N ; ++k ){
- t = sjeciste( pravci[ j ], pravci[ k ] );
- tocke.push_back( t );
- }
- }
- for( int j = 0 ; j < N ; ++j ){
- for( int k = 0 ; k < tocke.size() ; ){
- if( gt( udaljenost( tocke[ k ], pravci[ j ] ), 0.0 ) ){
- swap( tocke[ k ], tocke.back() );
- tocke.pop_back();
- } else {
- ++k;
- }
- }
- }
- bool answer= false;
- double tr, drugi;
- for( int j = 0 ; j < tocke.size() ; ++j ){
- bool tmp = true;
- for( int k = 0 ; k < N ; ++k ){
- if( j == k ) continue;
- tr = tocke[ j ].x * niz[ i ][ 0 ];
- tr += tocke[ j ].y * niz[ i ][ 1 ];
- tr += niz[ i ][ 2 ];
- drugi = tocke[ j ].x * niz[ k ][ 0 ];
- drugi += tocke[ j ].y * niz[ k ][ 1 ];
- drugi += niz[ k ][ 2 ];
- if( ! lt( tr, drugi ) ){
- tmp = false;
- break;
- }
- }
- answer |= tmp;
- }
- printf( "%d %d %s\n", i, tocke.size(), answer ? "Yes" : "No" );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement