Pagini recente » Cod sursa (job #3250283) | Cod sursa (job #3235407) | Cod sursa (job #2768094) | Cod sursa (job #670687) | Cod sursa (job #2605766)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#define NMAX 1500
#define EPSILON 1e-3
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
struct pct {
double x, y;
};
struct Pair {
int k;
double d;
};
int n;
vector<pct> v;
vector<Pair> mat[NMAX];
bool cmp(Pair& a, Pair& b) {
return (a.d < b.d);
}
double dist(pct &a, pct &b) {
double p1 = a.x - b.x, p2 = a.y - b.y;
return p1 * p1 + p2 * p2;
}
void init() {
fin >> n;
pct p;
for (int i = 0;i < n;++i) {
fin >> p.x >> p.y;
v.push_back(p);
}
for (int i = 0;i < n;++i) {
for (int j = i+1;j < n;++j) {
double d = dist(v[i], v[j]);
mat[i].push_back({ j,d });
mat[j].push_back({ i,d });
}
sort(mat[i].begin(), mat[i].end(), cmp);
}
}
int search(int i,double d) {
int low = 0, high = n - 2;
while (low <= high) {
int mid = low + (high - low) / 2;
if (abs(mat[i][mid].d - d) < EPSILON && (mid==n-2 || abs(mat[i][mid + 1].d - d) > EPSILON))
return mid;
if (mat[i][mid].d < d || abs(mat[i][mid].d - d) < EPSILON)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int search2(int i, double d) {
int low = 0, high = n - 2;
while (low <= high) {
int mid = low + (high - low) / 2;
if (abs(mat[i][mid].d - d) < EPSILON && (mid == 0 || abs(mat[i][mid - 1].d - d) > EPSILON))
return mid;
if (mat[i][mid].d < d)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int solve() {
int nr = 0;
for(int i=0;i<n;++i)
for (int j = i + 1;j < n;++j) {
double d = dist(v[i], v[j]);
int k1 = search(i, d), k2 = search2(i, d);
nr += k1 - k2 - 1;
}
return nr/3;
}
int main()
{
init();
fout << solve();
return 0;
}