Cod sursa(job #2023623)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 19 septembrie 2017 10:15:57
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.7 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[i].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];
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);
        }
    }
    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;
}
inline bool Check(int x,int y,int val)
{
    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;
        }
        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,p1,p3)>eps)
        {
            l=mid+1;
            sol=mid;
        }
            else
        if(Determ(p2,p1,p3)>=-eps)
        {
            return 1;
        }
            else
        {
            r=mid-1;
        }
    }
    if((1+sol)%2) return 1;
    return 0;
}
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(latura[dl].ya>latura[dl].yb)
            {
                swap(latura[dl].xa,latura[dl].xb);
                swap(latura[dl].ya,latura[dl].yb);
            }
        }
    }
    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;
            lsta=v[i].first;
        }
    }
     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;
        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;
}