Cod sursa(job #127796)

Utilizator VmanDuta Vlad Vman Data 25 ianuarie 2008 00:05:10
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <stdio.h>

#define Nmax 808

struct punct { int x, y; };
struct line { int l; double m; };

int N,M,i,tot;
punct P[Nmax],W;
int sx[Nmax]; //punctele sortate dupa x
line L[Nmax][Nmax]; //liniile care intersecteaza o zona
int nr[Nmax]; //numarul de linii care intersecteaza o zona
int a[Nmax],b[Nmax],c[Nmax]; //coeficientii

void qsort(int st,int dr)
{
 int i=st,j=dr,m=sx[(st+dr)>>1],aux;
 while (i<=j)
       {
        while (sx[i]<m) ++i;
        while (m<sx[j]) --j;
        if (i<=j)
           {
            aux=sx[i];sx[i]=sx[j];sx[j]=aux;
            ++i;--j;
           }
       }
 if (i<dr) qsort(i,dr);
 if (st<j) qsort(st,j);
}

void qsortlines(int ind,int st,int dr)
{
 int i=st,j=dr;
 double m=L[ind][(st+dr)>>1].m;
 line aux;
 while (i<=j)
       {
        while (L[ind][i].m<m) ++i;
        while (m<L[ind][j].m) --j;
        if (i<=j)
           {
            aux=L[ind][i];L[ind][i]=L[ind][j];L[ind][j]=aux;
            ++i;--j;
           }
       }
 if (i<dr) qsortlines(ind,i,dr);
 if (st<j) qsortlines(ind,st,j);
}


void build()
{
 int i,j;
 double alfa,xx,yy;
 for (i=1;i<N;++i)
   if (sx[i]!=sx[i+1])
     for (j=1;j<=N;++j)
         if (((P[j].x<=sx[i])&&(P[j+1].x>=sx[i+1])) || ((P[j+1].x<=sx[i])&&(P[j].x>=sx[i+1])))
            {
             if (P[j+1].y==P[j].y) yy=P[j].y;
               else
                 {
                  alfa=(double)(P[j+1].x-P[j].x)/(P[j+1].y-P[j].y);
                  xx=(double)(sx[i+1]+sx[i])/2-P[j].x;
                  yy=(double)P[j].y+xx/alfa;
                 }
             L[i][++nr[i]].l=j;
             L[i][nr[i]].m=yy;
            }
}

void cauta()
{
 int st=0,dr=N,lo,hi,m,aux;
 //cauta banda
 if (W.x<sx[1]) return;
 while (st+1<dr)
       {
        m=(st+dr)>>1;
        if (sx[m]<W.x) st=m;
           else dr=m;
       }
 while ((sx[st+1]<W.x)&&(st<=N)) ++st;
 while ((sx[st]==sx[st+1])&&(st<=N)) ++st;
 if ((st==0)||(st>=N)) return;
 //cauta deasupra cator drepte se afla
 lo=1;hi=nr[st];
 while (lo+1<hi)
       {
        m=(lo+hi)>>1;

         if (P[L[st][m].l].x<P[L[st][m].l+1].x) aux=1;
         	else aux=-1;

         if ((double)(aux*(a[L[st][m].l]*W.x+b[L[st][m].l]*W.y+c[L[st][m].l]))>0) lo=m;
         	else hi=m;
       }
 //ups and downs
 m=lo;
 if (P[L[st][m].l].x<P[L[st][m].l+1].x) aux=1;
        else aux=-1;
 if ((double)aux*(a[L[st][m].l]*W.x+b[L[st][m].l]*W.y+c[L[st][m].l])<0) --m;
 if (P[L[st][m+1].l].x<P[L[st][m+1].l+1].x) aux=1;
        else aux=-1;
 if ((double)aux*(a[L[st][m+1].l]*W.x+b[L[st][m+1].l]*W.y+c[L[st][m+1].l])>0) ++m;
 //se afla deasupra unui nr impar de drepte
 if (m&1) ++tot;
}

int main()
{
 freopen("poligon.in","r",stdin);
 freopen("poligon.out","w",stdout);
 scanf("%d %d",&N,&M);
 for (i=1;i<=N;++i)
     {
      scanf("%d %d",&P[i].x,&P[i].y);
      sx[i]=P[i].x;
     }
 P[N+1]=P[1];
 for (i=1;i<=N;++i)
     {
      a[i]=P[i].y-P[i+1].y;
      b[i]=P[i+1].x-P[i].x;
      c[i]=P[i].x*P[i+1].y-P[i+1].x*P[i].y;
     }
 qsort(1,N);
 build();
 for (i=1;i<N;++i)
  if (sx[i]!=sx[i+1])
   qsortlines(i,1,nr[i]);
 for (i=0;i<M;++i)
     {
      scanf("%d %d",&W.x,&W.y);
      cauta();
     }
 printf("%d",tot);
 fclose(stdout);
 fclose(stdin);
 return 0;
}