Pagini recente » Cod sursa (job #2721428) | Cod sursa (job #2689641) | Cod sursa (job #404143) | Cod sursa (job #1833710) | Cod sursa (job #309911)
Cod sursa(job #309911)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
#define FIN "triang.in"
#define FOUT "triang.out"
#define MAXN 1500
#define PRECISION 0.001
#define egale(a,b) (fabs((a)-(b)) < PRECISION)
#define pdd pair<double, double>
#define mp make_pair
#define f first
#define s second
inline double sqr(double val) {
return val * val;
}
pdd V[MAXN];
int N, totals = 0;
bool operator <=(pdd &A, pdd &B) {
return A.f - B.f < PRECISION ||
egale(A.f, B.f) && A.s - B.s < PRECISION;
}
bool operator ==(pdd &A, pdd &B) { return egale(A.f, B.f) && egale(A.s, B.s); }
void cauta(pdd punct) {
int step, i;
for (step = 1; step < N; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < N && V[i+step] <= punct)
i += step;
if (punct == V[i])
totals ++;
}
void rez()
{
int i, j;
double m, n;
// hokay, so basically:
// luam oricare dreapta, si scoatem pt ea mediatoarea ei.
for (i=0; i < N; ++i)
for (j=i+1; j < N; ++j) {
double x1, y1, x2, y2, X, Y;
x1 = V[i].f, y1 = V[i].s;
x2 = V[j].f, y2 = V[j].s;
double len = sqr(x1-x2) + sqr(y1-y2);
/*
d.a = V[j].y - V[i].y;
d.b = V[i].x - V[j].x;
d.c = - V[j].y*V[i].x + V[i].y*V[j].x;
*/
// mediatoarea
if (!egale(y1, y2)) {
m = (x1 - x2) / (y2 - y1);
n = (y1 + y2) / 2 - m * (x1 + x2) / 2;
// y = mx+n
// sqr(x1-x) + sqr(y1-y) = len =>
// sqr(x1-x) + sqr(y1-m*x-n) = len
// ecuatie:
// x^2 (1 + m^2) + x(-2 x1 - 2 y1 m + 2 m n) + x1^2 + n^2 - 2 y1 n - len == 0
double A = 1 + sqr(m);
double B = -2*x1 - 2*y1*m + 2*m*n;
double C = sqr(x1) + sqr(y1) + sqr(n) - 2*y1*n - len;
double Delta = sqr(B) - 4*A*C;
assert(Delta >= 0);
Delta = sqrt(Delta);
// now see if it exists
X = (-B - Delta) / (2*A), Y = m*X + n;
cauta(mp(X, Y));
X = (-B + Delta) / (2*A), Y = m*X + n;
cauta(mp(X, Y));
} else { // dreapta mea e orizontala
X = (x1 + x2) / 2;
Y = y1 + sqrt(3*len)/2;
cauta(mp(X, Y));
Y = y1 - sqrt(3*len)/2;
cauta(mp(X, Y));
}
}
assert(totals % 3 == 0);
printf("%d\n", totals/3);
}
void citire()
{
int i;
freopen(FIN, "r", stdin);
freopen(FOUT,"w",stdout);
scanf("%d", &N);
double x, y;
for (i=0; i<N; ++i) {
scanf("%lf %lf", &x, &y);
V[i] = mp(x, y);
}
sort(V, V + N);
}
int main()
{
citire();
rez();
return 0;
}