Cod sursa(job #596798)

Utilizator cont_de_testeCont Teste cont_de_teste Data 19 iunie 2011 22:26:28
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
# include <algorithm>
# include <cstdio>
# include <cstring>
# include <cmath>
# include <vector>
using namespace std;

typedef double db;
const char *FIN = "triang.in", *FOU = "triang.out";
const double pi = 2.0 * acos (0.0), eps = 1e-6;

vector < pair <db, db> > V;
int N;

# define x first
# define y second

db sq (db X) {
    return X * X;
}

db absolute (db X) {
    return (X < 0.0 ? -X : X);
}

bool less (db a, db b) {
    if (a < b && absolute (b - a) > eps)
        return true;
    return false;
}

bool greater (db a, db b) {
    if (a > b && absolute (b - a) > eps)
        return true;
    return false;
}

bool cb (db a, db b, int st, int dr) {
    for (int mij = 0; st <= dr; ) {
        mij = st + dr >> 1;
        if (less (V[mij].x, a)) st = mij + 1;
        else if (greater (V[mij].x, a)) dr = mij - 1;
        else if (less (V[mij].y, b)) st = mij + 1;
        else if (greater (V[mij].y, b)) dr = mij - 1;
        else return true;
    }
    return false;
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 0; i < N; ++i) {
        db a, b;
        scanf ("%lf %lf", &a, &b);
        V.push_back (make_pair (a, b));
    }
    sort (V.begin (), V.end ());
    int echi = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            db unghi = atan2 (V[j].y - V[i].y, V[j].x - V[i].x), R = sqrt (sq (V[j].x - V[i].x) + sq (V[j].y - V[i].y));
            echi += cb (V[i].x + R * cos (unghi + pi / 3.0), V[i].y + R * sin (unghi + pi / 3.0), j + 1, N - 1);
            echi += cb (V[i].x + R * cos (unghi - pi / 3.0), V[i].y + R * sin (unghi - pi / 3.0), j + 1, N - 1);
        }
    }
    fprintf (fopen (FOU, "w"), "%d", echi);
}