Cod sursa(job #589219)

Utilizator stef93Stefan Gilca stef93 Data 11 mai 2011 15:56:22
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream> 
#include <iostream>
#include <algorithm> 
#include <cmath> 
using namespace std; 
 
 
int n,nrt,Log; 
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 q) 
{ 
    
int step,i=q; 
    
double dis; 
    
dis=dist(t,t1); 
    
for(step=Log,i=0;step>0;step>>=1) 
        
if((i+step<n) && (dis<=dist(t1,a[i+step])) && (dis<=dist(t,a[i+step]))) i+=step; 
    return i;
} 

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(); 
  for(Log=1;Log<n;Log<<=1);
  sort(a,a+n,compare); 
  for(i=0;i<n-2;i++)  
  for(j=i+1;j<n-1;j++)         
  {
                             int c=binary_search(a[i],a[j],j+1);
                            // cout<<i<<' '<<j<<' '<<c<<'\n';
                            // cout<<dist(a[i],a[j])<<' '<<dist(a[j],a[c])<<' '<<dist(a[c],a[i])<<'\n';
                             if(equal(dist(a[i],a[j]),dist(a[j],a[c]))&&equal(dist(a[j],a[c]),dist(a[c],a[i])))
                             nrt++;
  }
  ofstream("triang.out")<<nrt<<'\n'; 
  return 0; 
}