Cod sursa(job #2629329)

Utilizator enedumitruene dumitru enedumitru Data 20 iunie 2020 10:07:30
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("poligon.in"); ofstream g("poligon.out");
typedef long long ll;
const int N=805;
vector<int> v[N];
bool vertical;
int n,k,t[N];
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;
    f>>n>>m;
    for(int i=1;i<=n;i++) {f>>p[i].x>> p[i].y; t[i]=p[i].x;}
    precompute();
    int ans=0;
    for(int i=1;i<=m;i++)
    {   pct c;
        f>>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));
    }
    g<<ans; g.close(); f.close(); return 0;
}