Cod sursa(job #596958)

Utilizator SpiderManSimoiu Robert SpiderMan Data 20 iunie 2011 12:18:50
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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 sn = 0.866025, cs = 0.5, eps = 1e-3;

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

# define x first
# define y second

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

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

inline bool less (db a, db b) {
    return a - b < eps;
}

inline bool equal (db a, db b) {
    return absolute (a - b) < eps;
}

bool cb (db a, db b, int st) {
    int cnt = 1 << 11, i;
    for (i = st; cnt; cnt >>= 1)
        if (i + cnt < N && (less (V[i + cnt].x, a) || equal (V[i + cnt].x, a) && less (V[i + cnt].y, b)))
            i += cnt;
    return equal (V[i].x, a) && equal (V[i].y, b);
}

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 - 1; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            echi += cb (V[i].x + (V[j].x - V[i].x) * cs - (V[j].y - V[i].y) * sn, V[i].y + (V[j].x - V[i].x) * sn + (V[j].y - V[i].y) * cs, j + 1);
            echi += cb (V[i].x + (V[j].x - V[i].x) * cs + (V[j].y - V[i].y) * sn, V[i].y - (V[j].x - V[i].x) * sn + (V[j].y - V[i].y) * cs, j + 1);
        }
    }
    fprintf (fopen (FOU, "w"), "%d", echi);
}