Cod sursa(job #617488)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 1510
#define eps 0.001
#define x first
#define y second
pair <double, double> v[nmax];
int n, sol, r;
char u[nmax][nmax];
int search(int a, int b, double x, double y)
{
int m, p=0, i;
while (a<=b)
{
m=(a+b)/2;
if (fabs(v[m].x-x)<=eps)
{
p=m;
b=m-1;
} else
if (v[m].x<x) a=m+1; else
b=m-1;
}
if (!p) return 0;
for (i=p; i<=n; i++)
{
if (fabs(v[i].y-y)<=eps)
{
r=p;
return 1;
}
if (fabs(v[i].x-x)>eps) return 0;
}
return 0;
}
int main()
{
freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
scanf("%d", &n);
int i, j;
double m, x, y, medx, medy, lung, a, X, Y, ca, rad;
for (i=1; i<=n; i++) scanf("%lf %lf", &v[i].x, &v[i].y);
sort (v+1, v+n+1);
for (i=1; i<n; i++)
for (j=i+1; j<=n; j++)
if (!u[i][j])
{
x=v[j].x-v[i].x;
y=v[j].y-v[i].y;
lung=x*x+y*y;
rad=sqrt(3*lung/4);
if (!y)
{
X=(v[i].x+v[j].x)/2;
Y=v[i].y+rad;
} else
if (!x)
{
X=v[i].x+rad;
Y=(v[i].y+v[j].y)/2;
} else
{
m=y/x;
m=-1/m;
medx=(v[j].x+v[i].x)/2;
medy=(v[j].y+v[i].y)/2;
a=3*lung/4/(m*m+1);
a=sqrt(a);
ca=a;
X=a+medx;
a=sqrt(3*lung/4-(X-medx)*(X-medx));
if (m>0) Y=a+medy; else Y=medy-a;
}
r=-1;
sol+=search(1, n, X, Y);
if (r>-1)
{
u[i][j]=u[j][i]=u[i][r]=u[r][i]=u[j][r]=u[r][j]=1;
}
if (!y)
{
X=(v[i].x+v[j].x)/2;
Y=v[i].y-rad;
} else
if (!x)
{
X=v[i].x-rad;
Y=(v[i].y+v[j].y)/2;
} else
{
X=-ca+medx;
a=sqrt(3*lung/4-(X-medx)*(X-medx));
if (m<0) Y=a+medy; else Y=medy-a;
}
r=-1;
sol+=search(1, n, X, Y);
if (r>-1)
{
u[i][j]=u[j][i]=u[i][r]=u[r][i]=u[j][r]=u[r][j]=1;
}
}
printf("%d\n",sol);
}