Cod sursa(job #9256)

Utilizator moga_florianFlorian MOGA moga_florian Data 27 ianuarie 2007 12:45:36
Problema Patrate 3 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
using namespace std;
#include<fstream>

int n;
double x[1005],y[1005];

double modul(double a)
{
if(a<0)
  return -a;
return a;      
}

int search(double a,double b)
{
int li=1,lf=n,m;

while(li<=lf)
  {
  m=(li+lf)/2;
  
  if(modul(a-x[m])<0.0001&&modul(b-y[m])<0.0001)
     return 1;
  else
  if(a<x[m]||(modul(a-x[m])<0.0001&&b<y[m]))
        lf=m-1;
  else
        li=m+1;
  } 
return 0;  
}

int main()
{
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");

int i,j,k;
double aux,dx,dy,xm,ym;
fin>>n;
for(i=1;i<=n;i++)
   fin>>x[i]>>y[i];
   
for(i=1;i<=n;i++)
  {
  j=i;
  while(j/2&&(x[j/2]<x[j]||(modul(x[j/2]-x[j])<0.0001&&y[j/2]<y[j])))
      {
      aux=x[j/2];
      x[j/2]=x[j];
      x[j]=aux;
      
      aux=y[j/2];
      y[j/2]=y[j];
      y[j]=aux;
      
      j/=2;                                                        
      }                    
  }
  
i=n;
while(i>1)
 {
 aux=x[i];
 x[i]=x[1];
 x[1]=aux;
     
 aux=y[i];
 y[i]=y[1];
 y[1]=aux;
 
 i--;
 
 j=1;
 while(1)
   {
   k=2*j;
   if(k>i) break;
   if(k+1<=i&&(x[k+1]>x[k]||(modul(x[k+1]-x[k])<0.0001&&y[k+1]>y[k]))) k++;
   if(x[j]>x[k]||(modul(x[j]-x[k])<0.0001&&y[j]>y[k])) break;
   
   aux=x[j];
   x[j]=x[k];
   x[k]=aux;
     
   aux=y[k];
   y[k]=y[j];
   y[j]=aux;
   
   j=k;   
   }          
 }
int s1,s2,sol=0;
 
for(i=1;i<n;i++)
  for(j=i+1;j<=n;j++)
    {
    xm=(x[i]+x[j])/2;
    ym=(y[i]+y[j])/2;
    
    dx=xm-x[i];
    dy=ym-y[i];
    if(dx<0) dx=-dx;
    if(dy<0) dy=-dy;
    
    if(y[i]<y[j])
      {
      s1=search(xm+dy,ym-dx);
      s2=search(xm-dy,ym+dx);       
      }      
    else
      {
      s1=search(xm+dy,ym+dx);
      s2=search(xm-dy,ym-dx);       
      }
      
    if(s1*s2)
       sol++;
    }
fout<<sol/2<<"\n";

fin.close();
fout.close();

return 0;
}