Cod sursa(job #2322791)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 18 ianuarie 2019 12:49:18
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.61 kb
#include <bits/stdc++.h>

using namespace std;

const double mic=1e-9;

ifstream f("poligon.in");
ofstream g("poligon.out");

int n,m,i,j,ans,len,aib[60010];
pair<int,int> a[810];
vector<int> pct[60010];
vector<pair<int,int> > straight[60010];
vector<pair<int,pair<int,int> > > v[60010];
pair<pair<int,int>,pair<int,int> > struc[810];

void upd(int poz,int val)
{
    for(;poz<=60001;poz+=poz&-poz)
        aib[poz]+=val;
}
bool get(int poz)
{
    for(;poz;poz-=poz&-poz)
        if(aib[poz])
            return 1;
    return 0;
}

double gt(double y,pair<pair<int,int>,pair<int,int> > lex)
{
    double x0=lex.first.first,y0=lex.first.second,x1=lex.second.first,y1=lex.second.second;
    if(x0==x1)return x0;
    double m=(y0-y1)/(x0-x1);
    double n=(x0*y1-x1*y0)/(x0-x1);
    return (y-n)/m;
}

double dst(double x,double y,pair<double,double> X1,pair<double,double> X2)
{
    if(X1.first==X2.first)return abs(X1.second-y);
    double m=(X1.second-X2.second)/(X1.first-X2.first);
    double n=(X1.first*X2.second-X1.second*X2.first)/(X1.first-X2.first);
    return abs(m*x-y+n)/sqrt(m*m+1);
}

int fnd(int x,int y)
{
    int l=0,r=len,mi;
    while(l<r)
    {
        mi=(l+r)/2;
        if(x-gt(y,struc[mi])>mic)
            l=mi+1;
        else
            r=mi;
    }
    return l;
}

void ext(int x,int y)
{
    int poz=fnd(x,y);
    int i;
    for(i=max(1,poz-1);i<=min(len,poz+1);i++)
        if(make_pair(x,y)==struc[i].first)
            break;
    for(;i<len;i++)
        struc[i]=struc[i+1];
    len--;
}

void ad (int x,int y,pair<int,int> lex)
{
    int poz=fnd(x,y);
    if(!poz)poz++;
    for(int i=len+1;i>=poz+1;i--)
        struc[i]=struc[i-1];
    struc[poz]={{x,y},lex};
    len++;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[i].first>>a[i].second;
    a[n+1]=a[1];
    for(i=1;i<=n;i++)
    {
        if(a[i].second==a[i+1].second)
            straight[a[i].second].push_back({min(a[i].first,a[i+1].first)+1,max(a[i].first,a[i+1].first)+1});
        else
            if(a[i].second<a[i+1].second)
                v[a[ i ].second].push_back({a[i].first,a[i+1]}),v[a[i+1].second].push_back({-1,a[i+1]});
            else
                v[a[i+1].second].push_back({a[i+1].first,a[i]}),v[a[ i ].second].push_back({-1,a[ i ]});
    }
//    for(i=0;i<=120;i++)
//        if(v[i].size())
//        {
//            g<<v[i].size()<<' ';
//            for(auto it:v[i])
//                g<<it.first<<' '<<i<<' '<<it.second.first<<' '<<it.second.second<<"  ";
//            g<<'\n';
//        }
    for(i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        pct[y].push_back(x);
    }
    for(i=0;i<=60000;i++)
    {
        for(auto it:straight[i])
            upd(it.first,1),upd(it.second+1,-1);
        for(auto it:v[i])
            if(it.first==-1)
                ext(it.second.first,it.second.second);
            else
                ad (it.first,i,it.second);
//        if(pct[i].size())
//        {
//            g<<i<<'\n';
//            for(int j=1;j<=len;j++)
//                g<<struc[j].first.first<<' '<<struc[j].first.second<<" : "<<struc[j].second.first<<' '<<struc[j].second.second<<'\n';g<<'\n';
//        }
        for(auto it:pct[i])
        {
            if(get(it+1)){ans++;continue;}
            int val=fnd(it,i);
            if(dst(it,i,struc[val].first,struc[val].second)<mic){ans++;continue;}
            ans+=(val&1);
//            g<<"AAA: "<<val<<'\n';
        }
        for(auto it:straight[i])
            upd(it.first,-1),upd(it.second+1,1);
    }
    g<<ans;
    return 0;
}