Cod sursa(job #987758)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 21 august 2013 14:16:23
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 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,val;
    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)
         {
             if(vs[i+step]==p.x) {i+=step; break;}
             else if(vs[i+step]<p.x) i+=step;
         }
        nrs=i; if(nrs==ns) nrs--;
 
        lim=sect[nrs].size()-1;
        step=maxstep; val=-1;
        for(i=-1;step;step>>=1)
         if(i+step<=lim)
         {
             val=side(sect[nrs][i+step].ind,p);
             if(val==0) {i+=step; break;}
             else if(val<0) i+=step;
         }
 
        if(val==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;
}