Cod sursa(job #811367)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define eps 1e-3
#define nmax 1510
#define pd pair<double, double>
#define pb push_back
#define mp make_pair
#define f first
#define s second
int N;
vector<pd> V;
pd now;
double dist(pd A, pd B)
{
return sqrt((A.f - B.f) * (A.f - B.f) + (A.s - B.s) * (A.s - B.s));
}
bool BS(int start, pd A)
{
int left = start, right = N - 1, mid;
while(left <= right)
{
mid = (left + right) / 2;
if(fabs(A.f - V[mid].f) < eps)
{
if(fabs(A.s - V[mid].s) < eps)
return 1;
if(A.s < V[mid].s) right = mid - 1;
else left = mid + 1;
}else
{
if(A.f < V[mid].f) right = mid - 1;
else left = mid + 1;
}
}
return 0;
}
bool cmp(pd A, pd B)
{
if(fabs(A.f - B.f) < eps) return A.s < B.s;
else return A.f < B.f;
}
int main()
{
ifstream in("triang.in");
ofstream out("triang.out");
int i, j;
in >> N;
for(i = 1; i <= N; i++)
{
double X, Y;
in >> X >> Y;
V.pb(mp(X, Y));
}
sort(V.begin(), V.end(), cmp);
int ans = 0;
for(i = 0; i < N; i++)
for(j = i + 1; j < N; j++)
{
double L = dist(V[i], V[j]);
if(fabs(V[i].f - V[j].f) < eps)
{
now.f = V[i].f + L * sqrt(3.0) / 2.0;
now.s = (V[i].s + V[j].s) / 2.0;
if(BS(j + 1, now))
ans ++;
now.f = V[i].f - L * sqrt(3.0) / 2.0;
now.s = (V[i].s + V[j].s) / 2.0;
if(BS(j + 1, now))
ans ++;
continue;
}
if(fabs(V[i].s - V[j].s) < eps)
{
now.f = (V[i].f + V[j].f) / 2.0;
now.s = V[i].s + L * sqrt(3.0) / 2.0;
if(BS(j + 1, now))
ans ++;
now.f = (V[i].f + V[j].f) / 2.0;
now.s = V[i].s - L * sqrt(3.0) / 2.0;
if(BS(j + 1, now))
ans ++;
continue;
}
double x0 = (V[i].f + V[j].f) / 2.0, y0 = (V[i].s + V[j].s) / 2.0;
double m = (V[i].s - V[j].s) / (V[i].f - V[j].f);
m = (-1.0) / m;
double c = x0 * x0 - 3.0 * L * L / (4.0 * (m * m + 1.0));
double delt = sqrt(4 * x0 * x0 - 4.0 * c) / 2;
now.f = x0 + delt;
now.s = m * (now.f - x0) + y0;
if(BS(j + 1, now)) ans ++;
now.f = x0 - delt;
now.s = m * (now.f - x0) + y0;
if(BS(j + 1, now)) ans ++;
}
out << ans;
return 0;
}