Pagini recente » Cod sursa (job #144940) | Statistici Cirja Miruna (terrax15) | Diferente pentru runda/redsnow_3 intre reviziile 35 si 36 | Monitorul de evaluare | Cod sursa (job #492731)
Cod sursa(job #492731)
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
double const EPS=0.0001;
int const maxn=1500;
struct Pt{double x,y;} Z[maxn];int n;
bool eq(double u,double w)
{w-=u;if(0>w){w=-w;}return w<EPS;}
bool operator<(const Pt&A,const Pt&B)
{ bool b;
if(eq(A.x,A.y)){b=A.y<B.y;}
else{b=A.x<B.x;}
return b;
}
bool bsrch(int k, double x,double y)
{ int a=k,b=n-1,m,q,u=-1,w=-1,r=-1;
while(a<=b)
{ m=(a+b)/2;q=Z[m].x;
if(eq(q,x)){u=m;b=m-1;}
else{if(q<x){a=m+1;}else{b=m-1;}}
}
if(0<=u)
{ a=u;b=n-1;
while(a<=b)
{ m=(a+b)/2;q=Z[m].x;
if(eq(q,x)){w=m;a=m+1;}else{b=m-1;}
}
while(u<=w)
{ m=(u+w)/2;q=Z[m].y;
if(eq(q,y)){r=m;u=w+1;}
else{if(q<y){u=m+1;}else{w=m-1;}}
}
}
return (-1!=r);
}
int main()
{ ifstream is("triang.in");
ofstream os("triang.out");
is>>n;int i,j,c=0;
for(i=0;n>i;++i){is>>Z[i].x>>Z[i].y;}
make_heap(&Z[0],&Z[n]);
sort_heap(&Z[0],&Z[n]);
const double a1=0.5, b1=sqrt(3.0)/2.0,
a2=a1, b2=-b1;
for(i=0;i<n;i++)
{ for(j=i+1;j<n;j++)
{ double x1=Z[i].x,y1=Z[i].y,
x2=Z[j].x,y2=Z[j].y,dx=x2-x1,dy=y2-y1,
x=x1+dx*a1-dy*b1,y=y1+dx*b1+dy*a1;
int k=j+1;
if(bsrch(k,x,y)){++c;}
x=x1+dx*a2-dy*b2;y=y1+dx*b2+dy*a2;
if(bsrch(k,x,y)){++c;}
}
}
os<<c<<endl;
}