Cod sursa(job #1747716)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 25 august 2016 14:44:00
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.92 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

ifstream fin( "poligon.in" ); ofstream fout( "poligon.out" );

const int nmax = 800;
const int inf = 60000 + 1;
const double eps = 1e-8;
const double alfa = 3.785215 * M_PI / 180;
//const double alfa = 0 * M_PI / 180;

int n, nrf, nrf2;
struct pct{
    double x, y;

    pct() {}
    pct( double _x, double _y ) {
        x = _x, y = _y;
    }

    inline bool operator < ( const pct &a ) const {
        return ( (x != a.x) ? (x < a.x) : (y < a.y) );
    }
} v[ nmax + 1 ];

double f[ nmax + 2 ];
vector< pct > l[ nmax + 2 ];
vector< double > sp[ nmax + 2 ];

inline bool egal( double a, double b ) {
    return ( a - eps < b && b < a + eps );
}
inline bool mmse( double a, double b ) {
    return ( egal( a, b ) || a < b );
}
void calc_fasii() {
    f[ 0 ] = -inf;
    sort( f + 1, f + n + 1 );
    nrf = 0;

    for( int i = 0; i <= n; ) {
        int j = i;
        f[ nrf ++ ] = f[ i ];
        while ( j <= n && egal( f[ i ], f[ j ] ) ) {
            ++ j;
        }
        i = j;
    }
    -- nrf;
    f[ nrf + 1 ] = inf;
    for( nrf2 = 1; (nrf2 << 1) <= nrf + 1; nrf2 <<= 1 ) {
    }
}
double intersectia_cu_vert( pct a, pct b, double k ) {
    return (b.y - a.y) * (k - a.x) / (b.x - a.x) + a.y;
}
void calc_intersectii() {
    for( int i = 0; i <= nrf; ++ i ) {
        for( int j = 0; j < n; ++ j ) {
            pct a = v[ j ], b = v[ (j + 1) % n ];
            if ( a.x > b.x ) {
                pct aux = a; a = b; b = aux;
            }

            if ( a.x != b.x && mmse( a.x, f[ i ] ) && mmse( f[ i + 1 ], b.x ) ) {
                pct p;
                p.x = intersectia_cu_vert( a, b, f[ i ] );
                p.y = intersectia_cu_vert( a, b, f[ i + 1 ] );
                sp[ i ].push_back( p.x );
                l[ i ].push_back( p );
            }
        }
        l[ i ].push_back( pct( -inf, -inf ) );
        sp[ i ].push_back( -inf );
        sort( l[ i ].begin(), l[ i ].end() );
        sort( sp[ i ].begin(), sp[ i ].end() );
    }
}
int solve( pct x ) {
    int ans = 0;
    int fasie = 0;
    for( int step = nrf2; step > 0; step >>= 1 ) {
        if ( fasie + step <= nrf + 1 && f[ fasie + step ] <= x.x ) {
            fasie += step;
        }
    }

    if ( f[ fasie ] == x.x ) {
        for ( int step = (1 << 9); step > 0; step >>= 1 ) {
            if ( ans + step < ( int )sp[ fasie ].size() ) {
                if ( mmse( sp[ fasie ][ ans + step ], x.y ) ) {
                    if ( egal( sp[ fasie ][ ans + step ], x.y ) ) return 1;
                    ans += step;
                }
            }
        }
    } else {
        for( int step = (1 << 9); step > 0; step >>= 1 ) {
            if ( ans + step < ( int )l[ fasie ].size() ) {
                pct a, b;
                a = pct( f[ fasie ], l[ fasie ][ ans + step ].x );
                b = pct( f[ fasie + 1 ], l[ fasie ][ ans + step ].y );

                double yy = intersectia_cu_vert( a, b, x.x );
                if ( mmse( yy, x.y ) ) {
                    if ( egal( yy, x.y ) ) return 1;
                    ans += step;
                }
            }
        }
    }
    return (ans % 2);
}
void roteste( double &x, double &y ) {
    double beta;
    if ( y == 0 ) {
        beta = M_PI / 2;
    } else {
        beta = atan( x / y );
    }
    double a, b, l = sqrt( x * x + y * y ) * 2 * sin( alfa / 2 );
    beta = M_PI / 2 - alfa / 2 - beta;
    b = y - l * cos( beta );
    a = x + l * sin( beta );
    x = a, y = b;
}
int main() {
    int m;
    fin >> n >> m;
    for( int i = 0; i < n; ++ i ) {
        fin >> v[ i ].x >> v[ i ].y;
        roteste( v[ i ].x, v[ i ].y );
        f[ i + 1 ] = v[ i ].x;
    }
    calc_fasii();
    calc_intersectii();

    int ans = 0;
    for( int i = 0; i < m; ++ i ) {
        pct q;
        fin >> q.x >> q.y;
        roteste( q.x, q.y );
        ans += solve( q );
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}