Pagini recente » Cod sursa (job #1974700) | Cod sursa (job #3036366) | Cod sursa (job #452332) | Cod sursa (job #2595144) | Cod sursa (job #166154)
Cod sursa(job #166154)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define PDD pair<double, double>
#define EPS 1e-3
#define x first
#define y second
double CT = 0.5 * sqrt(3);
int N, cnt;
PDD v[2048];
inline int compare(const PDD &m, double xx, double yy)
{
if (m.x + EPS < xx) return -1;
if (xx + EPS < m.x) return +1;
if (m.y + EPS < yy) return -1;
if (yy + EPS < m.y) return +1;
return 0;
}
int BS(double xx, double yy)
{
int l, r, m, ok;
for (l = 1, r = N; l <= r; )
{
m = (l + r) / 2;
ok = compare(v[m], xx, yy);
if (ok < 0) l = m+1;
else if (ok > 0) r = m-1;
else return 1;
}
return 0;
}
int main(void)
{
int i, j;
double x3, y3;
freopen("triang.in", "r", stdin);
freopen("triang.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%lf %lf", &v[i].x, &v[i].y);
sort(v+1, v+N+1);
for (i = 1; i <= N; ++i)
for (j = i+1; j <= N; ++j)
{
x3 = v[i].x + (v[j].x-v[i].x) * 0.5 - (v[j].y-v[i].y) * CT;
y3 = v[i].y + (v[j].x-v[i].x) * CT + (v[j].y-v[i].y) * 0.5;
if (BS(x3, y3))
++cnt;
x3 = v[i].x + (v[j].x-v[i].x) * 0.5 + (v[j].y-v[i].y) * CT;
y3 = v[i].y - (v[j].x-v[i].x) * CT + (v[j].y-v[i].y) * 0.5;
if (BS(x3, y3))
++cnt;
}
printf("%d\n", cnt/3);
return 0;
}