Cod sursa(job #972485)

Utilizator andrettiAndretti Naiden andretti Data 11 iulie 2013 20:03:57
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 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 maxstep 1024
using namespace std;

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

struct point{ int x,y;} v[maxn],p;
struct muchie{ point p1,p2;} vm[maxn];

int n,m,ns,sol;
int vs[maxn],ad[maxn],bd[maxn],cd[maxn];
double i1[maxn],i2[maxn];
vector <pr> 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;}
    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(int k,int vx)
{
    return i1[k]-i2[k]*vx;
}

void calc(point a,point b,int k)
{
    ad[k]=b.y-a.y;
    bd[k]=a.x-b.x;
    cd[k]=a.y*b.x-a.x*b.y;
    i1[k]=-(1.0*cd[k])/bd[k];
    i2[k]=(1.0*ad[k])/bd[k];
}

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];

      vm[i].p1=v[i]; vm[i].p2=v[i+1];
      if(v[i].x>v[i+1].x) swap(vm[i].p1,vm[i].p2);
    }

    for(i=1;i<=n;i++) calc(vm[i].p1,vm[i].p2,i);

    for(i=1;i<ns;i++)
    {
        for(j=1;j<=n;j++)
            {
                if(vm[j].p1.x>vs[i]) continue;
                if(vm[j].p2.x<=vs[i]) continue;
                yy1=inter(j,vs[i]);
                yy2=inter(j,vs[i+1]);
                sect[i].pb(mp((yy1+yy2)/2,j));
            }
        sort(sect[i].begin(),sect[i].end(),cmps);
    }
}

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

void solve()
{
    int step,i,nrs,lim;
    for(int k=1;k<=m;k++)
    {
        fin>>p.x>>p.y;
        if(p.x<vs[1] || p.x>vs[ns]) continue;

        step=maxstep;
        for(i=0;step;step>>=1)
         if(i+step<=ns && vs[i+step]<=p.x)
          i+=step;
        nrs=i; if(nrs==ns) nrs--;

        lim=sect[nrs].size()-1;
        step=maxstep;
        for(i=-1;step;step>>=1)
         if(i+step<=lim && side(sect[nrs][i+step].ind,p)<=0)
          i+=step;
        if(side(i,p)==0) {sol++; continue;}

        if((i+1)%2==1) sol++;
    }
}

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

    cit();
    initialize();
    solve();
    fout<<sol;

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