Cod sursa(job #56681)

Utilizator moga_florianFlorian MOGA moga_florian Data 30 aprilie 2007 09:45:17
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.1 kb
#include<stdio.h>
#define Nmax 804

int x[Nmax],y[Nmax];
int f[Nmax];
int A[Nmax],B[Nmax],C[Nmax];
double mij[Nmax][Nmax];
int lin[Nmax][Nmax],l[Nmax],N,M,ult[60010];
int sh[60010];

int eplatura(int X,int Y)
{
int i,sx,sy,dx,dy;
for(i=1;i<=N;i++)
  {
  if(x[i] < x[i+1])
     sx=x[i],dx=x[i+1];
  else
     sx=x[i+1],dx=x[i];  
     
  if(y[i] < y[i+1])
     sy=y[i],dy=y[i+1];
  else
     sy=y[i+1],dy=y[i];
                 
  if(A[i]*X+B[i]*Y+C[i] == 0 && sx<=X&&X<=dx && sy<=Y&&Y<=dy)
     return 1;
  }
return 0;
}

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

for(i=1;i<=N;i++)
  fscanf(fin,"%d%d",&x[i],&y[i]);
x[N+1]=x[1];
y[N+1]=y[1];

//fasii
for(i=1;i<=N;i++)
  {
  f[i]=x[i];
  
  j=i;
  while(j/2 && f[j/2]<f[j])
     {
     f[j/2]^=f[j];
     f[j]^=f[j/2];
     f[j/2]^=f[j];
     
     j/=2;
     }               
  }
  
i=N;
while(i>1)
 {
 f[1]^=f[i];
 f[i]^=f[1];
 f[1]^=f[i];
 i--;
 
 j=1;
 while(1)
  {
  k=j<<1;
  if(k>i) break;
  if(k+1<=i && f[k+1]>f[k]) k++;
  if(f[j] >= f[k]) break;
  
  f[j]^=f[k];
  f[k]^=f[j];
  f[j]^=f[k];
  j=k;       
  }         
 }

nf=1;
for(i=2;i<=N;i++)
  if(f[i] != f[nf])
     f[++nf]=f[i];

//preprocesare ecuatiile dreptelor
int sx,sy,dx,dy;
for(i=1;i<=N;i++)
  {
  if(x[i] < x[i+1])
     sx=x[i],sy=y[i],dx=x[i+1],dy=y[i+1];
  else
     sx=x[i+1],sy=y[i+1],dx=x[i],dy=y[i];
     
  A[i]=dy-sy;
  B[i]=sx-dx;
  C[i]=sy*dx-sx*dy;
  }
  
//preprocesare matrice
for(i=1;i<nf;i++)
  for(j=1;j<=N;j++)
   if(B[j])
    {//dreapta j cu fasia f[i]-f[i+1]
     if(x[j] < x[j+1])
        sx=x[j],sy=y[j],dx=x[j+1],dy=y[j+1];
     else
        sx=x[j+1],sy=y[j+1],dx=x[j],dy=y[j];
     
     //cazuri
     if(dx<=f[i] || f[i+1]<=sx);
     else
     if(f[i]<=sx && dx<=f[i+1])
        {
        mij[i][++l[i]]=((double)sy+dy)/2.0;
        lin[i][l[i]]=j;
        }
     else
     if(f[i]<=sx && sx<f[i+1])
        {
        ynou= ((double)A[j]*f[i+1]+C[j])/(double)B[j];
        ynou=-ynou;
        
        mij[i][++l[i]]= ((double)sy+ynou)/2.0;
        lin[i][l[i]]= j;
        }
     else
     if(f[i]<=dx && dx<f[i+1])
        {
        ynou= ((double)A[j]*f[i]+C[j])/(double)B[j];
        ynou=-ynou;
        
        mij[i][++l[i]]= ((double)ynou+dy)/2.0;
        lin[i][l[i]]= j;              
        }                   
     else
        {
        ynou= ((double)A[j]*f[i+1]+C[j])/(double)B[j];
        ynou=-ynou;
        ynou2= ((double)A[j]*f[i]+C[j])/(double)B[j];
        ynou2=-ynou2;
        
        mij[i][++l[i]]= (ynou+ynou2)/2.0;
        lin[i][l[i]]= j;                            
        }
    }
    
for(i=1;i<=N;i++)
 if(x[i]==f[nf])
  {
  if(x[i+1]==f[nf])
    {
    if(y[i]<y[i+1])
       sy=y[i],dy=y[i+1];
    else
       sy=y[i+1],dy=y[i];           
       
    for(j=sy;j<=dy;j++)
       ult[j]=1;
    }
  else
    ult[y[i]]=1;                 
  }
  
//sortare matrice
int fas;
double aux;

for(fas=1;fas<nf;fas++)
  {
  for(i=1;i<=l[fas];i++)
     {
     j=i;
     while(j/2 && mij[fas][j/2]<mij[fas][j])
       {
       aux=mij[fas][j];
       mij[fas][j]=mij[fas][j/2];
       mij[fas][j/2]=aux;
       
       lin[fas][j]^=lin[fas][j/2];
       lin[fas][j/2]^=lin[fas][j];
       lin[fas][j]^=lin[fas][j/2];
       
       j/=2;        
       }                
     }
     
  i=l[fas];
  while(i>1)
    {
    aux=mij[fas][1];
    mij[fas][1]=mij[fas][i];
    mij[fas][i]=aux;
    
    lin[fas][1]^=lin[fas][i];
    lin[fas][i]^=lin[fas][1];
    lin[fas][1]^=lin[fas][i];
    i--;
    
    j=1;
    while(1)
      {
      k=j<<1;
      if(k>i) break;
      if(k+1<=i && mij[fas][k+1]>mij[fas][k]) k++;
      if(mij[fas][j]>=mij[fas][k]) break;
      
      aux=mij[fas][j];
      mij[fas][j]=mij[fas][k];
      mij[fas][k]=aux;
      
      lin[fas][j]^=lin[fas][k];
      lin[fas][k]^=lin[fas][j];
      lin[fas][j]^=lin[fas][k];
      j=k;
      }
    }    
  }
  
for(i=1;i<nf;i++)
  for(j=f[i];j<f[i+1];j++)
     sh[j]=i;
sh[f[nf]]=nf;

//interogarile
f[0]=-1;
f[nf+1]=70000;
int li,lf,m,X,Y,nr=0,indl,sol=0;

for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d",&X,&Y);
       
//  if(eplatura(X,Y))
//     sol++;
//  else
  {                                   
  li=0;
  lf=nf;
  
  while(lf-li>1)
    {
    m=(li+lf)>>1;
    if(X<f[m])
      lf=m;
    else li=m;       
    }
    
  if(f[lf]<=X && X<f[lf+1])
     li=lf;
     
  if(li==0);
  else
  if(li==nf)
    {
    if(X==f[nf] && ult[Y])
       sol++;        
    }
  else
    {
    fas=li;
    
    li=0;
    lf=l[fas];
    
    while(lf-li>1)
      {
      m=(li+lf)>>1;
      if(A[lin[fas][m]]*X+B[lin[fas][m]]*Y+C[lin[fas][m]]<0)
         li=m;
      else
         lf=m;
      }
      
    if(A[lin[fas][lf]]*X+B[lin[fas][lf]]*Y+C[lin[fas][lf]]<0)
       li=lf;
       
    if(li%2)
       sol++;
    }     
  }
  }

fprintf(fout,"%d\n",sol);

fclose(fin);
fclose(fout);
return 0;
}