Pagini recente » Cod sursa (job #3283969) | Cod sursa (job #154492) | Cod sursa (job #750938) | Cod sursa (job #2667609) | Cod sursa (job #2605756)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#define NMAX 1500
#define EPSILON 1e-4
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(vector<Pair> &m,double d) {
int low = 0, high = n - 2;
while (low <= high) {
int mid = low + (high - low) / 2;
if (abs(m[mid].d - d) < EPSILON && (mid==n-2 || abs(m[mid + 1].d - d) > EPSILON))
return mid;
if (m[mid].d < d || abs(m[mid].d - d) < EPSILON)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int solve() {
int nr = 0;
for(int i=0;i<n;++i)
for (int j = 0;j < n - 1;++j) {
int k = search(mat[i], mat[i][j].d);
while (k >= 0 && abs(mat[i][k].d - mat[i][j].d) < EPSILON) {
if(mat[i][k].k!=mat[i][j].k && abs(dist(v[mat[i][k].k],v[mat[i][j].k])-mat[i][j].d)<EPSILON)
++nr;
--k;
}
}
return nr/6;
}
int main()
{
init();
fout << solve();
return 0;
}