Cod sursa(job #112416)

Utilizator stef2nStefan Istrate stef2n Data 5 decembrie 2007 10:36:14
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.7 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define VALMAX 805
struct punct{int x,y;};
struct dreapta{double x1,y1,x2,y2;};
FILE *fin,*fout;
punct p[VALMAX],q[VALMAX];
dreapta d[VALMAX][VALMAX];
dreapta dv[VALMAX];
int nrd[VALMAX],nrdv=0;
int ordonat[VALMAX];
int n;

inline double min(double x, double y)
  {return (x<y)?x:y;}

inline double max(double x, double y)
  {return (x>y)?x:y;}

inline double distanta(double x1, double y1, double x2, double y2)
  {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

inline int coliniare(double x0, double y0, double x1, double y1, double x2, double y2)
  {double val=x0*y1+x1*y2+x2*y0-x0*y2-x1*y0-x2*y1;
   if(val<0.00001 && val>-0.00001)
     return 1;
   else
     return 0;}

int interior(double x0, double y0, double x1, double y1, double x2, double y2)
  {double d1,d2,d3;
   d1=distanta(x0,y0,x1,y1);
   d2=distanta(x0,y0,x2,y2);
   d3=distanta(x1,y1,x2,y2);
   return (d1+d2-d3 < 0.00001)&&(d1+d2-d3 > -0.00001);}

int apartine_latura(double x0, double y0, double x1, double y1, double x2, double y2)
  {if(coliniare(x0,y0,x1,y1,x2,y2) && interior(x0,y0,x1,y1,x2,y2))
     return 1;
   else
     return 0;}

int apartine_dv(double x, double y)
  {int li=0,ls=nrdv-1,k,gasit=0,raspuns,kini;
   while(li<=ls && !gasit)
       {k=(li+ls)/2;
        if(dv[k].x1-x<0.0001 && dv[k].x1-x>-0.0001)
          {gasit=1;
           raspuns=apartine_latura(x,y,dv[k].x1,dv[k].y1,dv[k].x2,dv[k].y2);
           kini=k;
           k++;
           while(k<nrdv && !raspuns && dv[kini].x1-dv[k].x1<0.0001 && dv[kini].x1-dv[k].x1>-0.0001)
                {raspuns=raspuns && apartine_latura(x,y,dv[k].x1,dv[k].y1,dv[k].x2,dv[k].y2);
                 k++;}
           k=kini-1;
           while(k>=0 && !raspuns && dv[kini].x1-dv[k].x1<0.0001 && dv[kini].x1-dv[k].x1>-0.0001)
                {raspuns=raspuns && apartine_latura(x,y,dv[k].x1,dv[k].y1,dv[k].x2,dv[k].y2);
                 k--;}}
        else if(dv[k].x1>x)
               ls=k-1;
             else
               li=k+1;}
   if(!gasit)
     return 0;
   else
     return raspuns;}

int pos(int li, int ls)
  {int i=0,j=-1;
   punct aux;
   int auxij=li+rand()%(ls-li+1);
   aux=q[li];
   q[li]=q[auxij];
   q[auxij]=aux;
   while(li<ls)
       {if(q[li].x>q[ls].x)
          {aux=q[li];
           q[li]=q[ls];
           q[ls]=aux;
           auxij=i;
           i=-j;
           j=-auxij;}
        li+=i;
        ls+=j;}
   return li;}

void quicksort(int li, int ls) /* ordonare a punctelor dupa abscisa */
  {if(li<ls)
     {int k=pos(li,ls);
      quicksort(li,k-1);
      quicksort(k+1,ls);}}

int pos2(dreapta dd[805], int li, int ls)
  {int i=0,j=-1;
   dreapta aux;
   int auxij=li+rand()%(ls-li+1);
   aux=dd[li];
   dd[li]=dd[auxij];
   dd[auxij]=aux;
   while(li<ls)
       {if(dd[li].y1+dd[li].y2 > dd[ls].y1+dd[ls].y2)
          {aux=dd[li];
           dd[li]=dd[ls];
           dd[ls]=aux;
           auxij=i;
           i=-j;
           j=-auxij;}
        li+=i;
        ls+=j;}
   return li;}

void quicksort2(dreapta dd[805], int li, int ls)
  {if(li<ls)
     {int k=pos2(dd,li,ls);
      quicksort2(dd,li,k-1);
      quicksort2(dd,k+1,ls);}}

int pos3(int li, int ls)
  {int i=0,j=-1;
   dreapta aux;
   int auxij=li+rand()%(ls-li+1);
   aux=dv[li];
   dv[li]=dv[auxij];
   dv[auxij]=aux;
   while(li<ls)
       {if(dv[li].x1>dv[ls].x1)
          {aux=dv[li];
           dv[li]=dv[ls];
           dv[ls]=aux;
           auxij=i;
           i=-j;
           j=-auxij;}
        li+=i;
        ls+=j;}
   return li;}

void quicksort3(int li, int ls)
  {if(li<ls)
     {int k=pos3(li,ls);
      quicksort3(li,k-1);
      quicksort3(k+1,ls);}}

int cauta_binar(double x, double y) /*  se cauta binar banda in care se
                                       gaseste punctul (x,y) */
  {int gasit=0,li=0,ls=n-2,poz,k,COUNT=0;
   dreapta dd;
   double ycoresp,a,b,c;
   while(li<=ls && !gasit)
       {k=(li+ls)/2;
        if(q[k].x<x+0.0001 && x<q[k+1].x+0.0001)
          /*  daca punctul se incadreaza in banda curenta  */
          {gasit=1;
           poz=k;}
        else if(q[k].x>x)
               ls=k-1;
             else
               li=k+1;}
   if(!gasit)
     return 0;
   else /*  s-a gasit banda de pe pozitia poz -> acum se numara cate drepte
           sunt "deasupra" */
     {if(!ordonat[poz])
        {ordonat[poz]=1;
         quicksort2(d[poz],0,nrd[poz]-1);}
      li=0;
      ls=nrd[poz]-1;
      while(li<=ls)
          {k=(li+ls)/2;
           dd=d[poz][k];
           a=dd.y1-dd.y2;
           b=dd.x2-dd.x1;
           c=dd.x1*dd.y2-dd.x2*dd.y1;
           /* se verifica daca dreapta dd este "deasupra" */
           ycoresp=(-a*x-c)/b;
           if(ycoresp>y+0.00001)
             {COUNT+=(ls-k+1);
              ls=k-1;}
           else if(ycoresp<y-0.00001)
                  li=k+1;
                else
                  return 1;}}
   return COUNT%2;}


int main()
{
int i,j,m,count=0,np;
double x,y;
double a,b,c,x1,y1,x2,y2,minim,maxim;
fin=fopen("poligon.in","r");
fscanf(fin,"%d %d",&n,&m);
srand(n+m);
for(i=0;i<n;i++)
   {fscanf(fin,"%d %d",&p[i].x,&p[i].y);
    q[i]=p[i];}
quicksort(0,n-1);
for(i=0;i<n;i++)
   nrd[i]=0;
p[n]=p[0];
np=n;
i=0;
int in_plus=0;
while(i<n-1)
    {if(q[i].x==q[i+1].x)
       {q[i].x=-99999;
        in_plus++;}
     i++;}
i=0;j=0;
while(i<n)
    {if(q[i].x!=-99999)
       q[j++]=q[i];
     i++;}
n-=in_plus;
for(i=0;i<np;i++)
   {a=p[i].y-p[i+1].y;
    b=p[i+1].x-p[i].x;
    c=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
    minim=min(p[i].x,p[i+1].x);
    maxim=max(p[i].x,p[i+1].x);
    if(b) /* doar daca dreapta nu este verticala */
      for(j=0;j<n-1;j++)
         {/*  (x1,y1) este punctul de intersectie al dreptei de ecuatie
             a*x+b*y+c=0 cu dreapta de ecuatie x=q[j].x */
          x1=q[j].x;
          y1=(-a*x1-c)/b;
          /*  (x2,y2) este punctul de intersectie al dreptei de ecuatie
             a*x+b*y+c=0 cu dreapta de ecuatie x=q[j+1].x */
          x2=q[j+1].x;
          y2=(-a*x2-c)/b;
          /* doar daca (x1,y1) si (x2,y2) sunt pe latura poligonului */
          if(minim<x1+0.0001 && x1<maxim+0.0001)
            if(minim<x2+0.0001 && x2<maxim+0.0001)
              /* se adauga segmentul determinat la banda j */
              {d[j][nrd[j]].x1=x1;
               d[j][nrd[j]].y1=y1;
               d[j][nrd[j]].x2=x2;
               d[j][nrd[j]].y2=y2;
               nrd[j]++;}}
    else /* se retine dreapta verticala ca poate se gasesc puncte pe ea */
      {dv[nrdv].x1=p[i].x;
       dv[nrdv].y1=p[i].y;
       dv[nrdv].x2=p[i+1].x;
       dv[nrdv++].y2=p[i+1].y;}}
for(i=0;i<n-1;i++)
   ordonat[i]=0;
quicksort3(0,nrdv-1);
for(i=0;i<m;i++)
  {fscanf(fin,"%lf %lf",&x,&y);
   if(cauta_binar(x,y) || apartine_dv(x,y))
     count++;}
fclose(fin);
fout=fopen("poligon.out","w");
fprintf(fout,"%d\n",count);
fclose(fout);
return 0;
}