Cod sursa(job #972080)

Utilizator andrettiAndretti Naiden andretti Data 10 iulie 2013 22:32:55
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 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;
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("%lf%lf",&v[i].x,&v[i].y); vs[i]=v[i].x; }
    for(i=1;i<=m;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    v[n+1]=v[1]; v[0]=v[n]; vs[0]=-1;
}

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+n+1,cmpx);
    for(i=1;i<=n;i++)
     if(vs[i]!=vs[i-1])
       vs[++ns]=vs[i];

    for(i=1;i<=ns;i++)
    {
        for(j=1;j<=n;j++)
            if( vs[i]>=min(v[j].x,v[j+1].x) && vs[i]<max(v[j].x,v[j+1].x) )
                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 nrs,poz=0;
    int fst,lst;

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

    nrs=binary_sect(1,ns,k);
    fst=sect[nrs][0].ind;
    lst=sect[nrs][sect[nrs].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 %d",k,nrs);
    poz=binary_isect(0,sect[nrs].size()-1,k,nrs);// printf(" %d ",poz);
    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\n",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\n",sol);

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