Cod sursa(job #967905)

Utilizator andrettiAndretti Naiden andretti Data 28 iunie 2013 20:09:32
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 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
using namespace std;

struct point{ double x,y;};
point v[maxn],p[maxm];
int n,m,ns,sol;
int uz[maxm];
double vs[maxn];
vector < pair<double,int> > sect[maxn];

void cit()
{
    int i;
    int xi,yi;

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

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

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

void initialize()
{
    int i,j;

    sort(vs+1,vs+ns+1,cmpx);
    for(i=1;i<ns;i++)
    {
        for(j=1;j<=n;j++)
        {
            if( (v[j].x<vs[i] && v[j+1].x>vs[i]) || ( v[j].x>vs[i] && v[j+1].x<vs[i]) )
            {
                sect[i].pb(mp((v[j].y+v[j+1].y)/2,j));
                continue;
            }
            if( ( v[j].x==vs[i] && v[j+1].x!=vs[i]) || (v[j+1].x==vs[i] && v[j].x!=vs[i]) )
               sect[i].pb(mp((v[j].y+v[j+1].y)/2,j));
        }
        sort(sect[i].begin(),sect[i].end(),cmps);
    }
}

double side(point a,point b,point c)
{
    double aux=(c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
    if(a.x<b.x) return aux;
    return -aux;
}

int binary_sect(int st,int dr,int k)
{
    if(dr==st+1) return st;

    int mid=(st+dr)/2;
    if(p[k].x==vs[mid]) return mid;
    else
     if(p[k].x<vs[mid]) return binary_sect(st,mid,k);
     else return binary_sect(mid,dr,k);
}

int binary_isect(int st,int dr,int k,int nrs)
{
    if(dr==st+1) return st;

    int mid=(st+dr)/2;
    int nr=sect[nrs][mid].ind;
    double val=side(v[nr],v[nr+1],p[k]);

    if(val==0) return -1;
    else
     if(val<0)  return binary_isect(mid,dr,k,nrs);
     else return binary_isect(st,mid,k,nrs);
}


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

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

    sectnum=binary_sect(1,ns,k);
    fst=sect[sectnum][0].ind;
    lst=sect[sectnum][sect[sectnum].size()-1].ind;
    //printf("%d  %d   ",fst,lst);
    if(side(v[fst],v[fst+1],p[k])>0) return 0;
    if(side(v[lst],v[lst+1],p[k])<0) return 0;

    //printf("%d",sectnum);
    poz=binary_isect(0,sect[sectnum].size()-1,k,sectnum); if(poz==-1) return 1;

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

void solve()
{
    for(int i=1;i<=m;i++) sol+=search(i);
     //printf("%d ",search(i));
}

void afis()
{
    for(int i=1;i<=ns;i++) printf("%lf ",vs[i]); printf("\n");
    int k;
    for(k=1;k<ns;k++)
    {
        for(unsigned int i=0;i<sect[k].size();i++) printf("%lf %d--",sect[k][i].yy,sect[k][i].ind);
        printf("\n");
    }
}

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

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

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