Cod sursa(job #309907)

Utilizator sandyxpSanduleac Dan sandyxp Data 1 mai 2009 13:51:42
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#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 && A.s - B.s < PRECISION; }

bool operator ==(pdd &A, pdd &B) { return fabs(A.f-B.f)<PRECISION && fabs(A.s-B.s)<PRECISION; }

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;
}