Cod sursa(job #112410)

Utilizator stef2nStefan Istrate stef2n Data 5 decembrie 2007 10:01:55
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.52 kb
#include<stdio.h>
#include<math.h>
#include <algorithm>
using namespace std;
#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 n;

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

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

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

inline int coliniare(const double &x0, const double &y0, const double &x1, const double &y1, const double &x2, const 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(const double &x0, const double &y0, const double &x1, const double &y1, const double &x2, const 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);}

inline int apartine_latura(const double &x0, const double &y0, const double &x1, const double &y1, const double &x2, const 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(const double &x, const double &y)
  {int li=0,ls=nrdv-1,k,gasit=0,raspuns=0,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;}

bool cmp1(punct A, punct B) /* ordonare a punctelor dupa abscisa */
{
    return A.x<B.x;
}

bool cmp2(dreapta A, dreapta B)
{
    return A.y1+A.y2 < B.y1+B.y2;
}

bool cmp3(dreapta A, dreapta B)
{
    return A.x1<B.x1;
}

int cauta_binar(const double &x, const double &y) /*  se cauta binar banda in care se
                                                   gaseste punctul (x,y) */
  {int gasit=0,li=0,ls=n-2,poz=0,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" */
     {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&1;}


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);
for(i=0;i<n;i++)
   {fscanf(fin,"%d %d",&p[i].x,&p[i].y);
    q[i]=p[i];}
sort(q,q+n,cmp1);
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++)
    sort(d[i],d[i]+nrd[i],cmp2);
sort(dv,dv+nrdv,cmp3);
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;
}