Cod sursa(job #2038844)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 octombrie 2017 00:40:51
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.01 kb
#include<bits/stdc++.h>
#define maxN 805
#define eps 0.0000001
using namespace std;

int dv;
pair<int,int> zone[maxN];
vector<pair<int,int> >lst[maxN];
pair<int,int> v1[maxN],v[maxN];
int n,m;
int verticals[maxN];
vector<pair<pair<long double,long double>,pair<long double,long double> > > segm[maxN];
bool cmp(pair<pair<long double,long double>,pair<long double,long double> > a,pair<pair<long double,long double>,pair<long double,long double> > b)
{
    long double mid1=(a.first.second+a.second.second)/2.0;
    long double mid2=(b.first.second+b.second.second)/2.0;
    return mid1<mid2;
}
inline void Precalc()
{
    for(int i=1;i<dv;i++)
    {
        int l,r;
        l=zone[i].first;
        r=zone[i].second;
        for(vector<pair<int,int> >::iterator it=lst[i].begin();it!=lst[i].end();it++)
        {
            pair<int,int> p1=v[it->first];
            pair<int,int> p2=v[it->second];
            long double m=(p2.second-p1.second)/(p2.first-p1.first);
            int y0=p1.second;

            pair<long double,long double> lft={(long double)l,(long double)p1.second+m*(1.0*(l-p1.first))};
            pair<long double,long double> rgh={(long double)r,(long double)p1.second+m*(1.0*(r-p1.first))};

            segm[i].push_back({lft,rgh});
        }
    }

    for(int i=1;i<dv;i++)
    {
        sort(segm[i].begin(),segm[i].end(),cmp);
    }
}
inline long double Determ(pair<long double,long double> a,pair<long double,long double> b,pair<long double,long double> c)
{
    long double det=(long double)((c.first-a.first)*(b.second-a.second)-(b.first-a.first)*(c.second-a.second));
    return 0.5*det;
}

inline int Solve(int z,long double x,long double y)
{
    int st=0;
    int dr=segm[z].size()-1;
    int sol=-1;
    pair<long double,long double> p={(long double)x,(long double)y};
    while(st<=dr)
    {
        int mid=(st+dr)>>1;
        pair<pair<long double,long double>,pair<long double,long double>  > pr=segm[z][mid];
        pair<long double,long double> p1=pr.first;
        pair<long double,long double> p2=pr.second;
        if(Determ(p1,p,p2)<eps &&  Determ(p1,p,p2)>-eps) return 1;
        if(Determ(p1,p,p2)>=-eps)
        {
            sol=mid;
            st=mid+1;
        }
            else dr=mid-1;
    }
    return (sol+1)%2;
}
int main()
{
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    //    scanf("%d%d",&v[i].first,&v[i].second);
        fin>>v[i].first>>v[i].second;
        v1[i]=v[i];
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n;i++)
    {
        if(i==1 || v[i].first!=v[i-1].first) verticals[++dv]=v[i].first;
    }
    for(int i=1;i<dv;i++)
        zone[i]={verticals[i],verticals[i+1]};

    for(int i=1;i<=n;i++) v[i]=v1[i];
    for(int i=1;i<=n;i++)
    {
        int l,r;
        l=i;
        r=i+1;
        if(r>n) r=1;
        //if(v[l].first!=v[r].first)
        {
            for(int j=1;j<dv;j++)
            {
                pair<int,int> p1=v[l];
                pair<int,int> p2=v[r];
                if(p1.first>p2.first)
                {
                    swap(l,r);
                    swap(p1,p2);
                }
                if(p1.first<=zone[j].first && p2.first>=zone[j].second) lst[j].push_back({l,r});
            }
        }
    }


    Precalc();

    int ans=0;
    for(int i=1;i<=m;i++)
    {
        long double x,y;
        fin>>x>>y;
    //    cerr<<x<<' '<<y<<'\n';
        int st,dr;
        st=1;
        dr=dv-1;
        int sol;
        if(x<zone[1].first || x>zone[dv-1].second) continue;
        while(st<=dr)
        {
            int mid=(st+dr)>>1;
            if(zone[mid].first<=x)
            {
                sol=mid;
                st=mid+1;
            }
                else dr=mid-1;
        }
        int z=Solve(sol,x,y);
        if(!z && sol>1) Solve(sol-1,x,y);
        ans=ans+z;
      //  if(!z) qry[mid].push_back({x,y});
    }
    fout<<ans<<'\n';
    return 0;
}