Pagini recente » Cod sursa (job #2315440) | Cod sursa (job #1040038) | Cod sursa (job #444491) | Cod sursa (job #2247452) | Cod sursa (job #492832)
Cod sursa(job #492832)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
double const E=0.001;
int const maxn=1500;
struct Pt{double x,y;} Z[maxn];int L[maxn],n;
bool eq(double u,double w)
{w-=u;if(0>w){w=-w;}return w<E;}
bool operator<(const Pt&A,const Pt&B)
{ bool b;
if(A.x<B.x){b=true;}
else{if(A.x>B.x){b=false;}else{b=A.y<B.y;}}
return b;
}
int bsrch(int k,double x,double y)
{ int a=k,b=n-1,m,t=-1;double q;
while(a<=b)
{ m=(a+b)/2;q=Z[m].x;
if(eq(q,x)){t=m;b=m-1;}
else{if(q<x){a=m+1;}else{b=m-1;}}
}
if(0<=t)
{ a=t;b=a+L[a]-1;t=-1;
while(a<=b)
{ m=(a+b)/2;q=Z[m].y;
if(eq(q,y)){t=m;a=b+1;}
else{if(q<y){a=m+1;}else{b=m-1;}}
}
}
return t;
}
int main()
{ ifstream is("triang.in");
ofstream os("triang.out");
is>>n;int i,j,c=0,k;
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]);
for(i=1,j=0;n>i;++i)
{if(!eq(Z[i].x,Z[i].y)){L[j]=(i-j);j=i;}}
L[j]=n-j;
const double a1=0.5, b1=sqrt(3.0)/2.0,
a2=a1, b2=-b1;
for(i=0;i+2<n;i++)
{ for(j=i+1;j+1<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;
k=bsrch(j+1,x,y);
if(-1!=k)
{ ++c;
//os<<i<<' '<<j<<' '<<k<<endl;
}
x=x1+dx*a2-dy*b2;y=y1+dx*b2+dy*a2;
k=bsrch(j+1,x,y);
if(-1!=k)
{ ++c;
//os<<i<<' '<<j<<' '<<k<<endl;
}
}
}
os<<c<<endl;
}