Pagini recente » Cod sursa (job #2281391) | Cod sursa (job #1889751) | Cod sursa (job #2266087) | Cod sursa (job #3159600) | Cod sursa (job #2891879)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define eps 1e-3
#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;
}
int cmp(double a, double b)
{
if (a - b > eps)
return 1;
if (a - b < -eps)
return -1;
return 0;
}
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 check(int index1, int index2, int index3)
{
if (!cmp(dist[index1][index3], dist[index2][index3]))
if (!cmp(dist[index1][index3], dist[index1][index2]))
return 1;
return 0;
}
int binary_search(int index1, int index2)
{
int i, step;
for (step = 1; step <= n; step <<= 1);
for (i = max(index1, index2); step; step >>= 1)
if (i + step <= n && check(index1, index2, i + step))
i += step;
return i;
}
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);
precalc();
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
int r = binary_search(i, j);
//cout << r << " <- R\n\n";
if (check(i, j, r) == 1)
++cnt;
}
/*for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
cout << dist[i][j] << ' ';
cout << '\n';
}*/
fout << cnt << '\n';
fin.close();
fout.close();
return 0;
}