Cod sursa(job #2032030)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 4 octombrie 2017 12:21:40
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.86 kb
#include<bits/stdc++.h>
#define maxN 805
#define inf 1000000
#define eps 0.0000001
#define pdd pair<long double,long double>
using namespace std;
typedef struct type
{
    long double xa,ya,xb,yb;
};
type latura[maxN];
pair<long double,long double> v[maxN];
bool cmp(int i,int j)
{
    long double mid1=(latura[i].ya+latura[i].yb)/2.0;
    long double mid2=(latura[j].ya+latura[j].yb)/2.0;
    return mid1<mid2;
}
bool vert[maxN];
int n,dv,dl;
long double verticals[maxN];
long double st[maxN][maxN],dr[maxN][maxN];
long double delta1,delta2,delta3,delta4;
vector<int> lst[maxN],lst2[maxN];
inline void Precalc()
{
    for(int i=1;i<=dl;i++)
    {
        for(int j=1;j<dv;j++)
        {
            if(verticals[j]>=latura[i].xa && verticals[j]<=latura[i].xb) lst[j].push_back(i);
                    else
            if(vert[i] && fabs(verticals[j]-latura[i].xa)<eps) lst[j].push_back(i);
        }
    }
    for(int i=1;i<dv;i++)
    {
        for(auto it:lst[i])
        {
            lst2[i].push_back(it);
        }
        for(auto it:lst[i+1])
        {
            lst2[i].push_back(it);
        }

    }
    for(int i=1;i<=dv;i++)
    {
        lst[i].clear();
        for(auto it:lst2[i])
            lst[i].push_back(it);
    }
    for(int j=1;j<dv;j++)
    {
        sort(lst[j].begin(),lst[j].end(),cmp);
        int sz=lst[j].size();
        for(int k=0;k<sz;k++)
        {
            //if(latura[lst[j][k]].xa==latura[lst[j][k]].xb) st[k]=
           // if(vert[lst[j][k]]) continue;
            long double panta=(latura[lst[j][k]].yb-latura[lst[j][k]].ya)/(latura[lst[j][k]].xb-latura[lst[j][k]].xa);
            delta1=verticals[j]-latura[lst[j][k]].xa;
            delta2=delta1*panta;
            st[j][k]=latura[lst[j][k]].ya+delta2;
            delta3=delta1+verticals[j+1]-verticals[j];
            delta4=delta3*panta;
            dr[j][k]=delta4+latura[lst[j][k]].ya;
        }
    }
}
inline long double Determ(pdd p1,pdd p2,pdd p3)
{
    long double determ=p1.first*p2.second+p1.second*p3.first+p2.first*p3.second-p3.first*p2.second-p1.first*p3.second-p2.first*p1.second;
    determ=0.5*determ;
    return determ;
}
vector<pair<int,int> > lstvert[maxN];
inline bool Check(int x,int y,int val)
{
    if(x==verticals[val])
    for(vector<pair<int,int> >::iterator it=lstvert[val].begin();it!=lstvert[val].end();it++)
    {
        if(it->first<=y && it->second>=y) return 1;
    }
    int l,r,sol;
    l=0;
    r=lst[val].size()-1;
    sol=-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
     //   if(vert[lst[val][mid]])
        {
            if(latura[lst[val][mid]].xa==x && latura[lst[val][mid]].ya<=y && latura[lst[val][mid]].yb>=y)
            {
                return 1;
            }
                else
            if(latura[lst[val][mid]].yb<y)
            {
                l=mid+1;
                sol=mid;
            }
                else r=mid-1;
            continue;
        }
        pair<long double,long double> p1=make_pair((long double)verticals[val],(long double)st[val][mid]);
        pair<long double,long double> p2=make_pair((long double)verticals[val+1],(long double)dr[val][mid]);
        pair<long double,long double> p3=make_pair((long double)x,(long double)y);
        if(Determ(p2,p3,p1)>eps)
        {
            l=mid+1;
            sol=mid;
        }
            else
        if(Determ(p2,p3,p1)>=-eps)
        {
            return 1;
        }
            else
        {
            r=mid-1;
        }
    }
    if((1+sol)%2) return 1;
    return 0;
}
map<int,int> M;
int m;
int ans=0;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int main()
{
  //  freopen("poligon.in","r",stdin);
  //  freopen("poligon.out","w",stdout);
   // scanf("%d%d",&n,&m);
    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;
    }
    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)
        {
            latura[++dl]={v[l].first,v[l].second,v[r].first,v[r].second};
            if(latura[dl].xa>latura[dl].xb)
            {
                swap(latura[dl].xa,latura[dl].xb);
                swap(latura[dl].ya,latura[dl].yb);
            }
        }
        if(v[l].first==v[r].first)
        {
        //    vert[dl]=1;
            if(v[l].second>v[r].second)
            {
                swap(v[l],v[r]);
            //    swap(latura[dl].xa,latura[dl].xb);
             //   swap(latura[dl].ya,latura[dl].yb);
            }
          //  lstvert[M.find(v[l].first)].push_back(make_pair(v[l].second,v[r].second));
        }
    }
    sort(v+1,v+n+1);
    v[n+1]={inf,inf};
    int lsta=-1;
    for(int i=1;i<=n+1;i++)
    {
        if(v[i].first!=lsta)
        {
            verticals[++dv]=v[i].first;
            M[v[i].first]=dv;
            lsta=v[i].first;
        }
    }
    for(int i=1;i<=n;i++)
    {
       int  l=i;
       int  r=i+1;
        if(r>n) r=1;
        if(v[l].first==v[r].first)
        {
             lstvert[M[v[l].first]].push_back(make_pair(v[l].second,v[r].second));
        }
    }
     int x,y;
    Precalc();
    for(int i=1;i<=m;i++)
    {

       // scanf("%d%d",&x,&y);
        fin>>x>>y;
        int l,r;
        l=1;
        r=dv-1;
        if(verticals[1]>x) continue;
        if(verticals[dv-1]<x) continue;
        int mid=0,sol=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(verticals[mid]<=x)
            {
                sol=mid;
                l=mid+1;
            }
                else
                {
                    r=mid-1;
                }
        }
        if(Check(x,y,sol)) ans++;
    }
    fout<<ans<<'\n';
   // printf("%d\n",ans);
    return 0;
}