Cod sursa(job #972173)

Utilizator andrettiAndretti Naiden andretti Data 11 iulie 2013 10:38:58
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include<fstream>
#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;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

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;

    fin>>n>>m;
    for(i=1;i<=n;i++){ fin>>v[i].x>>v[i].y; vs[i]=v[i].x; }
    for(i=1;i<=m;i++) fin>>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; }

double inter(point a,point b,double vx)
{
    return ((vx-a.x)*(b.y-a.y))/(b.x-a.x)+a.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<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) )
            {
                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);
    }
}

double side(point a,point b,point c)
{
    if(a.x>b.x) swap(a,b);
    return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}

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;

    if(side(v[fst],v[fst+1],p[k])>0) return 0;
    if(side(v[lst],v[lst+1],p[k])<0) return 0;
    if(side(v[lst],v[lst+1],p[k])==0) return 1;

    poz=binary_isect(0,sect[nrs].size()-1,k,nrs);
    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);

}

int main()
{
    cit();
    initialize();
    solve();
    fout<<sol<<'\n';

    fin.close();
    fout.close();
    return 0;
}