Cod sursa(job #1865112)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 februarie 2017 13:49:01
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.8 kb
#include <bits/stdc++.h>
using namespace std;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
} in( "poligon.in" );
fstream out( "poligon.out", ios::out );

const double EPS = 1e-8;

vector<pair<double, double>> plg; vector<vector<pair<double, double>>> lst1;
vector<double> col; vector<vector<pair<pair<double, double>, pair<double, double>>>> lst2;

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 ( sl1.first.second + sl1.second.second ) < ( sl2.first.second + sl2.second.second );
}

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( col[pos] == pt.first && lst1[pos].size() > 0 && sgn( pt.second - lst1[pos].front().first ) >= 0 && sgn( pt.second - lst1[pos].back().second ) <= 0 ) {
        int le = 0, ri = lst1[pos].size() - 1;
        while( le <= ri ) {
            int md = le + ( ri - le ) / 2;

            if( lst1[pos][md].second < pt.second )
                le = md + 1;
            else
                ri = md - 1;
        }

        if( lst1[pos][le].second <= pt.second )
            return true;
    }

    if( pos != 0 )
        pos --;

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

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

    return ( le % 2 );
}

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() );
    lst1.resize( col.size() ); lst2.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 )
            lst1[lower_bound( col.begin(), col.end(), pt1.first ) - col.begin()].push_back(
                make_pair( min( pt1.second, pt2.second ), max( pt1.second, pt2.second ) ) );
        else {
            for( int j = 0; j < lst2.size(); j ++ ) {
                if( pt1.first <= col[j] && col[j + 1] <= pt2.first )
                    lst2[j].push_back( make_pair( isg( pt1, pt2, col[j] ), isg( pt1, pt2, col[j + 1] ) ) );
            }
        }
    }

    for( int i = 0; i < lst1.size(); i ++ )
        sort( lst1[i].begin(), lst1[i].end() );
    for( int i = 0; i < lst2.size(); i ++ )
        sort( lst2[i].begin(), lst2[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;
}