Cod sursa(job #1865139)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 februarie 2017 14:19:26
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.91 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "poligon.in" , ios::in  );
fstream out( "poligon.out", ios::out );

const double EPS = 1e-8;

vector<pair<double, double>> plg;
vector<double> col; vector<vector<pair<pair<double, double>, pair<double, double>>>> lst;

inline int sgn( double x ) {
    if( fabs( x ) < EPS )
        return 0;
    return ( x < 0 ) ? -1 : 1;
}

inline pair<double, double> isg( pair<double, double> pt1, pair<double, double> pt2, double pos ) {
    return make_pair( pos, pt1.second + ( pt2.second - pt1.second ) * ( pos - pt1.first ) / ( pt2.first - pt1.first ) );
}

inline bool cmp( pair<pair<double, double>, pair<double, double>> sl1, pair<pair<double, double>, pair<double, double>> sl2 ) {
    return sgn( ( sl1.first.second + sl1.second.second ) - ( sl2.first.second + sl2.second.second ) ) < 0;
}

inline double ccw( pair<double, double> pt1, pair<double, double> pt2, pair<double, double> pt3 ) {
    return ( pt2.first - pt1.first ) * ( pt3.second - pt1.second ) -
           ( pt3.first - pt1.first ) * ( pt2.second - pt1.second );
}

bool slv( pair<double, double> pt ) {
    int pos = lower_bound( col.begin(), col.end(), pt.first ) - col.begin();

    if( pt.first < col.front() || pt.first > col.back() )
        return false;

    if( pos != 0 )
        pos --;

    int le = 0, ri = lst[pos].size() - 1;
    while( le <= ri ) {
        int md = le + ( ri - le ) / 2;

        if( sgn( ccw( lst[pos][md].first, lst[pos][md].second, pt ) ) >= 0 )
            le = md + 1;
        else
            ri = md - 1;
    }

    if( ri == -1 )
        return false;

    return ( ( le % 2 ) || sgn( ccw( lst[pos][ri].first, lst[pos][ri].second, pt ) ) == 0 );
}

int main( void ) {
    ios::sync_with_stdio( false );

    int n, m;
    in >> n >> m;

    for( int i = 0; i < n; i ++ ) {
        int x, y;
        in >> x >> y;

        plg.push_back( make_pair( x, y ) );
        col.push_back( x );
    }

    plg.push_back( plg.front() ); sort( col.begin(), col.end() );
    col.resize( unique( col.begin(), col.end() ) - col.begin() );
    lst.resize( col.size() - 1 );

    for( int i = 1; i < plg.size(); i ++ ) {
        pair<double, double> pt1 = plg[i - 1], pt2 = plg[i];

        if( pt1.first > pt2.first )
            swap( pt1, pt2 );

        if( pt1.first != pt2.first ) {
            for( int j = 0; j < lst.size(); j ++ ) {
                if( pt1.first <= col[j] && col[j + 1] <= pt2.first )
                    lst[j].push_back( make_pair( isg( pt1, pt2, col[j] ), isg( pt1, pt2, col[j + 1] ) ) );
            }
        }
    }

    for( int i = 0; i < lst.size(); i ++ )
        sort( lst[i].begin(), lst[i].end(), cmp );

    int ans = 0;
    for( int i = 0; i < m; i ++ ) {
        int x, y;
        in >> x >> y;

        ans += slv( make_pair( x, y ) );
    }

    out << ans << endl;
    return 0;
}