Cod sursa(job #1663007)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 25 martie 2016 13:43:47
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include<fstream>
#include<vector>
#include<algorithm>

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;

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

    pct() {}
    pct( int _x, int _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 ];

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

void calc_fasii() {
    f[ 0 ] = 0;
    sort( f + 1, f + n + 1 );
    nrf = unique( f + 1, f + n + 1 ) - f;
    -- 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;
}
double egal( double a, double b ) {
    return ( a - eps < b && b < a + eps );
}
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 && a.x <= f[ i ] && 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 ] );
                l[ i ].push_back( p );
            }
        }
        l[ i ].push_back( pct( -1, -1 ) );
        sort( l[ i ].begin(), l[ i ].end() );
    }
}
int solve( pct x ) {
    int fasie = 0;
    for( int step = nrf2; step > 0; step >>= 1 ) {
        if ( fasie + step <= nrf + 1 && f[ fasie + step ] <= x.x ) {
            fasie += step;
        }
    }

    int ans = 0;
    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 ( yy < x.y ) {
                ans += step;
            }
        }
    }
    return (ans % 2);
}
int main() {
    int m;
    fin >> n >> m;
    for( int i = 0; i < n; ++ i ) {
        fin >> 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;
        ans += solve( q );
    }

    fout << ans << "\n";

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