Cod sursa(job #2327527)

Utilizator MAXIMILLIANMUSOHYEAHYEAH MAXIMILLIANMUS Data 24 ianuarie 2019 19:20:53
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
 
using namespace std;
ifstream in("poligon.in");
ofstream out("poligon.out");
typedef long long ll;
const int N = 805;
 
vector<int> v[N];
bool vertical;
int t[N],n,k;
double mid;
 
struct pct
{
    int x,y;
} p[N];
 
double eval(pct a, pct b, double m)
{
    return a.y+(b.y-a.y)*(m-a.x)/((double)b.x-a.x);
}
 
bool comp(int x, int y)
{
    return eval(p[x],p[x+1],mid)<eval(p[y],p[y+1],mid);
}
 
ll det(pct a, pct b, pct c)
{
    return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
 
bool compare(pct a, pct b)
{
    if (a.x == b.x)
        return a.y<b.y;
    return a.x<b.x;
}
 
bool ok(int i, pct a)
{
    ll D;
    if (compare(p[i],p[i+1]))
        D = det(p[i],p[i+1],a);
    else
        D = det(p[i+1],p[i],a);
    if (!D)
    {
        vertical = 1;
        return 1;
    }
    return D>0;
}
 
 
void precompute()
{
    sort(t+1,t+n+1);
    t[0] = -1;
    p[n+1] = p[1];
    for (int i = 1; i<=n; i++)
        if (t[i]!=t[k])
            t[++k] = t[i];
    t[k+1] = t[k]+100;
    for (int i = 1; i<=k; i++)
    {
        for (int j = 1; j<=n; j++)
            if ((p[j].x<=t[i]&&t[i+1]<=p[j+1].x)||(p[j+1].x<=t[i]&&t[i+1]<=p[j].x))
                v[i].push_back(j);
        mid = (double)(t[i]+t[i+1])/2;
        sort(v[i].begin(),v[i].end(),comp);
    }
}
 
int main()
{
    int m;
    in >> n >> m;
    for (int i = 1; i<=n; i++)
    {
        in >> p[i].x >> p[i].y;
        t[i] = p[i].x;
    }
 
    precompute();
 
    int ans = 0;
    for (int i = 1; i<=m; i++)
    {
        pct c;
        in >> c.x >> c.y;
        int poz = 0, cnt = -1;
        for (int i = 1<<9; i; i>>=1)
            if (poz+i<=k && t[poz+i]<c.x)
                poz+=i;
        vertical = 0;
        for (int i = 1<<9; i; i>>=1)
            if (cnt+i<v[poz].size() && ok(v[poz][i+cnt],c))
                cnt+=i;
        cnt++;
        ans+=((cnt&1)||(vertical));
    }
 
    out << ans;
}