Cod sursa(job #53693)

Utilizator moga_florianFlorian MOGA moga_florian Data 22 aprilie 2007 21:30:16
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include<stdio.h>
#define Nmax 803

int x[Nmax],y[Nmax];
int c[Nmax],l[Nmax];
double m[Nmax][Nmax];

int main()
{
FILE *fin=fopen("poligon.in","r"),
     *fout=fopen("poligon.out","w");
     
int N,M,i,j,k,n,X,Y;
fscanf(fin,"%d%d",&N,&M);

for(i=1;i<=N;i++)
  fscanf(fin,"%d%d",&x[i],&y[i]);
  
n=0;
for(i=1;i<=N;i++)
  {
  c[i]=x[i];
  j=i;
  while(j/2 && c[j/2]<c[j])
    {
    c[j/2]^=c[j];
    c[j]^=c[j/2];
    c[j/2]^=c[j];
    j/=2;        
    }
  }
  
i=N;
while(i>1)
 {
 c[i]^=c[1];
 c[1]^=c[i];
 c[i]^=c[1];
 i--;
 
 j=1;
 while(1)
  {
  k=j<<1;
  if(k>i) break;
  if(k+1<=i && c[k+1]>c[k]) k++;
  if(c[j] >= c[k]) break;
  
  c[j]^=c[k];
  c[k]^=c[j];
  c[j]^=c[k];
  j=k;       
  }       
 }
 
n=1;
for(i=2;i<=N;i++)         
   if(c[i] != c[i-1])
      c[++n]=c[i];
      
int st,dr,sty,dry;
double A,B,C,ny;
for(i=1;i<n;i++)
  //fasia c[i] - c[i+1]
  {
  for(j=1;j<N;j++)
    {
    if(x[j] < x[j+1])
       st=x[j],dr=x[j+1],sty=y[j],dry=y[j+1];
    else
       st=x[j+1],dr=x[j],sty=y[j+1],dry=y[j];
       
    if(dr<c[i] || c[i+1]<st);
    else
    if(c[i]<= st && dr<=c[i+1])
       m[i][++l[i]]= ((double)y[j]+(double)y[j+1]) / 2.0;
    else
    if(c[i]<=st && st<=c[i+1])
       {      
       A=(double)y[j+1] - y[j];
       B=(double)x[j] - x[j+1];
       C=(double)y[j]*(x[j+1]-x[j]) - (double)x[j]*(y[j+1]-y[j]);
       
       ny= (-C-A*c[i+1]) / B;
       
       m[i][++l[i]]= (ny+(double)sty) / 2.0;
       }       
    else
       {
       A=(double)y[j+1] - y[j];
       B=(double)x[j] - x[j+1];
       C=(double)y[j]*(x[j+1]-x[j]) - (double)x[j]*(y[j+1]-y[j]);

       ny= (-C-A*c[i]) / B;              
       
       m[i][++l[i]]= (ny+(double)dry) / 2.0;
       }       
    }           
    
    //cazu N - 1
    if(x[1] < x[N])
       st=x[1],dr=x[N],sty=y[1],dry=y[N];
    else
       st=x[N],dr=x[1],sty=y[N],dry=y[1];
       
    if(dr<c[i] || c[i+1]<st);
    else
    if(c[i]<= st && dr<=c[i+1])
       m[i][++l[i]]= ((double)y[1]+(double)y[N]) / 2.0;
    else
    if(c[i]<=st && st<=c[i+1])
       {      
       A=(double)y[N] - y[1];
       B=(double)x[1] - x[N];
       C=(double)y[1]*(x[N]-x[1]) - (double)x[1]*(y[N]-y[1]);
       
       ny= (-C-A*c[i+1]) / B;
       
       m[i][++l[i]]= (ny+(double)sty) / 2.0;
       }       
    else
       {
       A=(double)y[N] - y[1];
       B=(double)x[1] - x[N];
       C=(double)y[1]*(x[N]-x[1]) - (double)x[1]*(y[N]-y[1]);

       ny= (-C-A*c[i]) / B;              
       
       m[i][++l[i]]= (ny+(double)dry) / 2.0;
       }            
  }
  
int li,lf,mij,sol=0,nr;
for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&X,&Y);
  nr=0;
  
  li=1;lf=n-1;
  while(lf-li>1)
    {
    mij=(li+lf)>>1;
    if(X<=c[mij])
       lf=mij;
    else
       li=mij;       
    }  
  
  if(c[li]<= X && X<=c[li+1])
     {
     for(j=1;j<=l[li];j++)
       if(m[li][j] <= Y)
         nr++;
         
     if(nr%2)
       sol++;
     } 
  else
  if(c[lf]<= X && X<=c[lf+1])
     {
     for(j=1;j<=l[lf];j++)
       if(m[lf][j] <= Y)
         nr++;
         
     if(nr%2)
       sol++;                  
     }      
  }
         
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;         
}