Cod sursa(job #972316)

Utilizator andrettiAndretti Naiden andretti Data 11 iulie 2013 14:23:32
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define pr pair<double,int>
#define yy first
#define ind second
#define maxn 805
#define maxm 60005
#define maxstep 1024
using namespace std;

struct point{ int x,y;} v[maxn],p;
int n,m,ns,sol;
int vs[maxn],ad[maxn],bd[maxn],cd[maxn];
vector <pr> sect[maxn];

void cit()
{
    int i;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){ scanf("%d%d",&v[i].x,&v[i].y); vs[i]=v[i].x; }
    v[n+1]=v[1]; v[0]=v[n]; vs[0]=-1;
}

int cmpx(int a,int b) { return a<b; }
int cmps(pr a,pr b) { return a.yy<b.yy; }

double inter(point a,point b,int vx)
{
    return (1.0*(vx-a.x)*(b.y-a.y))/(b.x-a.x)+a.y;
}

void calc(point a,point b,int index)
{
    ad[index]=b.y-a.y;
    bd[index]=a.x-b.x;
    cd[index]=a.y*b.x-a.x*b.y;
}

void initialize()
{
    int i,j;
    double yy1,yy2;

    sort(vs+1,vs+n+1,cmpx);
    for(i=1;i<=n;i++)
     if(vs[i]!=vs[i-1])
       vs[++ns]=vs[i];

    for(i=1;i<=n;i++)
    {
        if(v[i].x>v[i+1].x) swap(v[i],v[i+1]);
        calc(v[i],v[i+1],i);
    }

    for(i=1;i<ns;i++)
    {
        for(j=1;j<=n;j++)
         if(v[j].x<=vs[i] && v[j+1].x>vs[i])
         {
           yy1=inter(v[j],v[j+1],vs[i]);
           yy2=inter(v[j],v[j+1],vs[i+1]);
           sect[i].pb(mp((yy1+yy2)/2,j));
         }

        sort(sect[i].begin(),sect[i].end(),cmps);
    }
}

long long int side(int index,point c)
{
    return ad[index]*c.x+bd[index]*c.y+cd[index];
}

int binary_sect()
{
    int step=maxstep;
    int i;
    for(i=0;step;step>>=1)
     if(i+step<=ns)
     {
         if(vs[i+step]==p.x) return i+step;
         else
          if(vs[i+step]<p.x) i+=step;
     }
     return i;
}

int binary_isect(int lim,int nrs)
{
    int step=maxstep,nr;
    double val;
    int i;
    for(i=-1;step;step>>=1)
     if(i+step<=lim)
     {
         nr=sect[nrs][i+step].ind;
         val=side(nr,p);
         if(val==0) return -1;
         else
          if(val<0) i+=step;
     }
    return i;
}


int search()
{
    int nrs,poz=0;
    int fst,lst;

    if(p.x<vs[1] || p.x>vs[ns]) return 0;

    nrs=binary_sect(); if(nrs==ns) nrs--;
    fst=sect[nrs][0].ind;
    lst=sect[nrs][sect[nrs].size()-1].ind;

    if(side(fst,p)>0) return 0;
    if(side(lst,p)<0) return 0;

    poz=binary_isect(sect[nrs].size()-1,nrs);
    if(poz==-1) return 1;

    if((poz+1)%2==1) return 1;
    return 0;
}

void solve()
{
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&p.x,&p.y);
        sol+=search();
    }
}

int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);

    cit();
    initialize();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}