Pagini recente » Cod sursa (job #331503) | Cod sursa (job #1419079) | Cod sursa (job #2291540) | Cod sursa (job #2933189) | Cod sursa (job #2891891)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define eps 0.0001
#define NMAX 1505
pair<double, double> v[NMAX];
int n;
double dist[NMAX][NMAX];
double pit(double a, double b)
{
return a*a + b*b;
}
void precalc()
{
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
dist[i][j] = pit(v[i].x - v[j].x, v[i].y - v[j].y);
dist[j][i] = dist[i][j];
}
}
int cmp(pair<double, double> a, pair<double, double> b)
{
if (abs(a.x - b.x) + abs(a.y - b.y) < eps)
return 1;
return 0;
}
int binary_search(int p, pair<double, double> s)
{
int st = p + 1, dr = n, mij;
while (st <= dr) {
mij = (st + dr) / 2;
if (cmp(v[mij], s) == 0) {
/*cout << mij << " <-MIJ\n";
cout << v[mij].x << ' ' << v[mij].y << '\n';
cout << s.x << ' ' << s.y << '\n';*/
return 1;
}
if (v[mij] < s)
st = mij + 1;
else
dr = mij - 1;
}
return 0;
}
int possible_point(int index1, int index2)
{
pair<double, double> z1, z2, mij;
mij.x = (v[index1].x + v[index2].x) / 2;
mij.y = (v[index1].y + v[index2].y) / 2;
double d = dist[index1][index2] * 3 / 4;
if (v[index1].y != v[index2].y) {
//cout << "NU EGALE\n";
double p = (v[index1].x - v[index2].x) / (v[index1].y - v[index2].y);
p = -p;
z1.x = mij.x + sqrt(d / (p * p + 1));
z1.y = mij.y + p * (z1.x - mij.x);
z2.x = mij.x - sqrt(d / (p * p + 1));
z2.y = mij.y + p * (z2.x - mij.x);
// cout << z1.x << ' ' << z1.y << ' ' << z2.x << ' ' << z2.y << '\n';
} else {
//cout << "EGALE\n";
z1.x = mij.x;
z1.y = mij.y + sqrt(d);
z2.x = mij.x;
z2.y = mij.y - sqrt(d);
// cout << z1.x << ' ' << z1.y << ' ' << z2.x << ' ' << z2.y << '\n';
}
int nr = binary_search(index2, z1);
nr += binary_search(index2, z2);
//cout << nr << " <- NR\n";
return nr;
}
int main()
{
ifstream fin("triang.in");
ofstream fout("triang.out");
int cnt = 0;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
/*for (int i = 1; i <= n; i++)
cout << v[i].x << ' ' << v[i].y << '\n';*/
precalc();
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
cnt += possible_point(i, j);
//cout << cnt << '\n';
fout << cnt << '\n';
fin.close();
fout.close();
return 0;
}