Cod sursa(job #1756371)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 12 septembrie 2016 18:33:44
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.75 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define pdd pair <int, int>

using namespace std;

const int NMAX = 800;
const int MAXVAL = 60000;
const double eps = 1e-4;

pair <int, int> v[NMAX+5];
vector <int> xfasii;
vector <pair <double, double> > fasii[NMAX+5];

vector <pair <int, int> > acopy;
vector <pair <int, int> > vert[MAXVAL+5];

bool cmp(pair <double, double> a, pair <double, double> b)
{
    return a.first + a.second < b.first + b.second;
}

double ccw(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    return (b.first - a.first)*(c.second - b.second) - (b.second - a.second)*(c.first - b.first);
}

int main()
{
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v[i] = pair <int, int> (x, y);
        xfasii.push_back(x);
        acopy.push_back(pair <int, int> (x, y));
    }
    sort(acopy.begin(), acopy.end());
    v[n] = v[0];
    sort(xfasii.begin(), xfasii.end());
    int pos = 0;
    for(int i=0; i<n; )
    {
        xfasii[pos++] = xfasii[i];
        while(i < n && xfasii[i] == xfasii[pos - 1]) i++;
    }
    int F = pos;

    for(int i=0; i<n; i++)
    {
        pair <int, int> a = v[i], b = v[i+1];
        if(a.first == b.first)
        {
            if(a.second < b.second)
                vert[a.first].push_back(pair <int, int> (a.second, b.second));
            else vert[a.first].push_back(pair <int, int> (b.second, a.second));
        }
    }
    for(int i=0; i<=60000; i++)
        sort(vert[i].begin(), vert[i].end());
    for(int k=0; k<F-1; k++)
    {
        for(int i=0; i<n; i++)
        {
            pair <int, int> a = v[i], b = v[i+1];
            if(a.first == b.first)continue;
            if(a.first > b.first)swap(a, b);
            if(xfasii[k] >= a.first && b.first > xfasii[k])
            {
                double t = (1.0*a.first - xfasii[k])/(xfasii[k] - b.first);
                double val1 = (a.second + b.second*t)/(t+1);

                double val2;
                if(xfasii[k+1] == b.first)val2 = b.second;
                else
                {
                    t = (1.0*a.first - xfasii[k+1])/(xfasii[k+1] - b.first);
                    val2 = (a.second + b.second*t)/(t+1);
                }
                fasii[k].push_back(pair <double, double> (val1, val2));
            }
        }
        sort(fasii[k].begin(), fasii[k].end(), cmp);
    }

    int ans = 0;
    for(int i=0; i<m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);

        vector <pair <int, int> > :: iterator it = lower_bound(acopy.begin(), acopy.end(), pair <int, int> (x, y));
        if(x == it->first && y == it->second)
        {
            ans++;
            continue;
        }
        if(vert[x].size() != 0)
        {
            int l = 0, r = vert[x].size()-1;
            bool found = false;
            while(l <= r)
            {
                int mid = (l+r)/2;
                if(vert[x][mid].first > y)
                    r = mid - 1;
                else if(vert[x][mid].second < y)
                    l = mid + 1;
                else
                {
                    found = true;
                    break;
                }
            }
            if(found)
            {
                ans++;
                continue;
            }
        }

        int st = 0, dr = F-1;
        int low = F;
        while(st <= dr)
        {
            int med = (st+dr)/2;
            if(xfasii[med] <= x)st = med + 1;
            else
            {
                dr = med - 1;
                low = med;
            }
        }
        if(low == F)continue;
        low--;
        //vector <int> :: iterator low = lower_bound(xfasii.begin(), xfasii.begin() + F, x);
        st = 0, dr = fasii[low].size() - 1;
        int low2 = -1;

        bool ok = true;
        while(st <= dr)
        {
            int med = (st+dr)/2;
            pdd x1 = pdd(xfasii[low], fasii[low][med].first);
            pdd x2 = pdd(xfasii[low+1], fasii[low][med].second);
            int val = ccw(x2, x1, pdd(x, y));
            if(val >= eps)dr = med-1;
            else if(val <= -eps)
            {
                st = med+1;
                low2 = med;
            }
            else
            {
                ans++;
                ok = false;
                break;
            }
        }
        //vector <pair <int, int> > :: iterator low2 = lower_bound(fasii[pos].begin(), fasii[pos].end(), y, cmp);
        if(ok && low2%2 == 0)ans++;
    }
    printf("%d\n", ans);
    return 0;
}