Cod sursa(job #1748039)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 25 august 2016 23:29:37
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define pdd pair <double, double>

using namespace std;

const int NMAX = 800;
const double eps = 1e-10;
const double sine = 0;
const double cosine = 1;
//const double sine = 0.1453787;
//const double cosine = 0.96824111657311335544346580317146;

pair <double, double> v[NMAX+5];
vector <double> xfasii;
vector <pair <double, double> > fasii[NMAX+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);
        double a = x*cosine - y*sine;
        double b = x*sine + y*cosine;
        v[i] = pair <double, double> (a, b);
        xfasii.push_back(a);
    }
    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 && fabs(xfasii[i] - xfasii[pos - 1]) < eps) i++;
    }
    int F = pos;

    for(int k=0; k<F-1; k++)
    {
        for(int i=0; i<n; i++)
        {
            pair <double, double> 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 > -eps && b.first - xfasii[k] >= eps)
            {
                double t = (a.first - xfasii[k])/(xfasii[k] - b.first);
                double val1 = (a.second + b.second*t)/(t+1);

                double val2;
                if(fabs(xfasii[k+1] - b.first) < eps)val2 = b.second;
                else
                {
                    t = (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;
    //scanf("%d", &m);
    for(int i=0; i<m; i++)
    {
        double x, y;
        scanf("%lf%lf", &x, &y);

        double a = x*cosine - y*sine;
        double b = x*sine + y*cosine;
        x=a;y=b;

        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 <double> :: 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);
            double 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 <double, double> > :: iterator low2 = lower_bound(fasii[pos].begin(), fasii[pos].end(), y, cmp);
        if(ok && low2%2 == 0)ans++;
    }
    printf("%d\n", ans);
    return 0;
}