Cod sursa(job #2324537)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 20 ianuarie 2019 22:25:49
Problema Poligon Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.07 kb
#include <bits/stdc++.h>
#define det(A,B,C) (A.first*B.second+B.first*C.second+C.first*A.second)-(C.first*B.second+B.first*A.second+A.first*C.second)

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];

//bool jeof[210][210];

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

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)
{
//    cout<<x<<' '<<y<<' '<<X1.first<<' '<<X1.second<<' '<<X2.first<<' '<<X2.second<<'\n';
    if(abs(X1.first-X2.first)<mic)return abs(X1.first-x);
    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=1,r=len+1,mi;
    while(l<r)
    {
        mi=(l+r)/2;
        if(gt(y,struc[mi])-x>mic)
            r=mi;
        else
            l=mi+1;
    }
    return l;
}

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

void ad (int x,int y,pair<int,int> lex)
{
//    g<<"ADD:\n";
//    g<<x<<' '<<y<<' '<<lex.first<<' '<<lex.second<<'\n';
//    g<<"TO\n";
//    for(int i=1;i<=len;i++)
//        g<<struc[i].first.first<<' '<<struc[i].first.second<<' '<<struc[i].second.first<<' '<<struc[i].second.second<<'\n';
//    g<<"DONE\n\n";
    int poz=fnd(x,y);
    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;
        straight[a[i].second].push_back({a[i].first+1,a[i].first+1});
    }
    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=0;i<=20;i++)
//        for(j=0;j<=20;j++)
//            pct[j].push_back(i);

    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);
        sort(v[i].begin(),v[i].end());
        for(j=1;j<v[i].size();j++)
            if(v[i][j].first==v[i][j-1].first&&v[i][j].first!=-1)
                if(det(v[i][j].second,make_pair(v[i][j].first,i),v[i][j-1].second)>0)
                    swap(v[i][j],v[i][j-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)-1;
            if(1<=val&&val<=len)if(dst(it,i,struc[val].first,struc[val].second)<mic){ans++;continue;}
            ans+=(val&1);
//            g<<it<<' '<<i<<'\n'<<dst(it,i,struc[val].first,struc[val].second)<<'\n';
//            g<<"AAA: "<<val<<'\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:straight[i])
            upd(it.first,-1),upd(it.second+1,1);

    }
//    for(i=20;i>=0;i--)
//    {
//        if(i>=10)
//            g<<i<<": ";
//        else
//            g<<i<<" : ";
//        for(j=0;j<=20;j++)
//            g<<jeof[j][i];
//        g<<'\n';
//    }
    g<<ans<<'\n';
    return 0;
}