Pagini recente » Cod sursa (job #1350986) | Cod sursa (job #504524) | Cod sursa (job #936434) | training_round_1 | Cod sursa (job #474254)
Cod sursa(job #474254)
#include<fstream>
#include<algorithm>
#include<cmath>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;
const char iname[]="triang.in";
const char oname[]="triang.out";
const int maxn=1505;
ifstream f(iname);
ofstream g(oname);
punct a[maxn];
double eps=1e-3,aux=sqrt(3);
int n,i,j,k,ans,step;
inline int cmp(double a,double b)
{
if(a+eps<b)
return -1;
if(b+eps<a)
return 1;
return 0;
}
inline int cmp(punct a,punct b)
{
int d=cmp(a.x,b.x);
if(d)
return d;
return cmp(a.y,b.y);
}
punct get(punct a,punct b)
{
return make_pair(0.5*((a.x+b.x)+aux*(a.y-b.y)),0.5*((b.y+a.y)+aux*(b.x-a.x)));
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{
punct aux=get(a[i],a[j]);
if(cmp(aux,a[j])>0)
{
for(step=1;step<(n-j);step<<=1);
for(k=j;step;step>>=1)
if(k+step<=n&&cmp(a[k+step],aux)<=0)
k+=step;
if(cmp(a[k],aux)==0)
++ans;
}
aux=get(a[j],a[i]);
if(cmp(aux,a[j])>0)
{
for(step=1;step<(n-j);step<<=1);
for(k=j;step;step>>=1)
if(k+step<=n&&cmp(a[k+step],aux)<=0)
k+=step;
if(cmp(a[k],aux)==0)
++ans;
}
}
g<<ans<<"\n";
}