Cod sursa(job #57299)

Utilizator moga_florianFlorian MOGA moga_florian Data 1 mai 2007 18:04:10
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
using namespace std;
#include<fstream>
#include<math.h>
#define Nmax 1506
#define eps 0.001

double x[Nmax],y[Nmax];
int b1,N;

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

int search(double x0,double y0,int j)
{
int ind=0,i;

for(i=b1;i;i>>=1)
  if( x[ind+i] <= x0 )
     ind+=i;

i=ind;
while(i && modul(x[i]-x0) < eps )
  {
  if( modul(y[i]-y0) <eps && ind>j)
      return 1;
  i--;     
  }
  
i=ind;
while(i<=N &&modul(x[i]-x0) < eps )
  {
  if( modul(y[i]-y0) <eps && ind>j)
      return 1;
  i++;     
  }
return 0;     
}

void intersc(int i,int j)
{
double aux;
aux=x[i];
x[i]=x[j];
x[j]=aux;

aux=y[i];
y[i]=y[j];
y[j]=aux;    
}

int comp(int i,int j)
{
if(x[i]<x[j])
  return -1;
if(x[i]>x[j]) 
  return 1;    

if(y[i]<y[j])
  return -1;
if(y[i]>y[j])
  return 1;
  
return 0;
}

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

int i,j,k;
double rad=1.73205;
fin>>N;

b1=1;
while( b1 <= N ) b1<<=1;
b1>>=1;

for(i=1;i<=N;i++)
   fin>>x[i]>>y[i];
   
for(i=1;i<=N;i++)
   {
   j=i;
   while(j/2 && comp(j/2,j)<0 )        
      {
      intersc(j/2,j);
      j/=2;       
      }   
   }
   
i=N;
while(i>1)
  {
  intersc(1,i);
  i--;
  
  j=1;
  while(1)
   {
   k=j<<1;
   if(k>i) break;
   if(k+1<=i && comp(k,k+1)<0 ) k++;
   if(comp(j,k)>=0) break;
   
   intersc(j,k);
   j=k;       
   }        
  }
  
//calculare 
int sol=0;
double p,xm,ym,x0,y0,d,dif,A,B,C,delta,p1,p2;

for(i=1;i<N;i++)
  for(j=i+1;j<=N;j++)
    {
    xm=(x[i]+x[j])/2.0;
    ym=(y[i]+y[j])/2.0;
    
    if( modul(x[i] - x[j]) < eps)
       {
       d=modul(y[i]-y[j]);
       
       x0=xm;
       dif=(d*rad)/2.0;
       y0=ym+dif;       
       if(search(x0,y0,j))
          sol++;
          
       y0=ym-dif;
       if(search(x0,y0,j))
          sol++;       
       }
    else
    if( modul(y[i] - y[j]) < eps)
       {
       d=modul(x[i]-x[j]);
       
       y0=ym;
       dif=d*rad/2.0;
       x0=xm+dif;
       
       if(search(x0,y0,j))
          sol++;
          
       x0=xm-dif;
       if(search(x0,y0,j))
          sol++;                   
       }
    else
       {
       p=(y[j]-y[i])/(x[j]-x[i]);
       p=(-1.0)/p;
       d=(x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
       
       dif=ym-p*xm-y[i];
       A=p*p+1.0;
       B=2*p*dif-2*x[i];
       C=x[i]*x[i] + dif*dif - d;
       
       delta=B*B-4*A*C;
       delta=sqrt(delta);
       
       x0= (-B + delta)/(2.0*A);
       y0= p*x0+ym-p*xm;
       
       if(search(x0,y0,j))
          sol++;
          
       x0= (-B-delta)/(2.0*A);
       y0= p*x0+ym-p*xm;
              
       if(search(x0,y0,j))
          sol++;                   
       }                     
    }
    
fout<<sol<<"\n";
fin.close();
fout.close();
return 0;    
}