Cod sursa(job #589208)

Utilizator stef93Stefan Gilca stef93 Data 11 mai 2011 15:27:08
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream> 
#include <algorithm> 
#include <cmath> 
using namespace std; 
 
 
int n,nrt; 
struct P{double x,y;}a[1503]; 
 
 
double dist(P x,P y) 
{ 
    
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y); 
} 
 
 
bool equal(double x,double y) 
{ 
    
if (fabs(x-y)>1e-3)return 0; 
    
return 1; 
} 
 
 
bool compare(P t, P yt) 
{ 
    
return t.x>yt.x; 
} 
 
 
int binary_search(P t,P t1) 
{ 
    
int step,i; 
    
double dis; 
    
dis=dist(t,t1); 
    
for(step=1,i=0;step<n;step<<=1) 
        
if((i+step<n) &&((t.x<t1.x)&&(a[i+step].x>t1.x)) && (dis<=dist(t1,a[i+step])) && (dis<=dist(t,a[i+step]))) i+=step; 
    
if(equal(dis,dist(t1,a[i]))&&equal(dis,dist(t,a[i]))) return 1; 
        
return 0; 
} 

int main() 
{ 
  int i,j,k; 
  ifstream in("triang.in"); 
  in>>n; 
  for(i=0;i<n;i++)  
                    in>>a[i].x>>a[i].y; 
  in.close(); 
  sort(a,a+n,compare); 
  for(i=0;i<n;i++)  
  for(j=i+1;j<n;j++)         
  if(binary_search(a[i],a[j]))                
  nrt++; 
  ofstream("triang.out")<<nrt<<'\n'; 
  return 0; 
}