Cod sursa(job #292093)

Utilizator MariusMarius Stroe Marius Data 30 martie 2009 19:12:04
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <set>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const char iname[] = "triang.in";
const char oname[] = "triang.out";

#define FOR(i, a, b)  for (int i = (int)(a); i < (int)(b); ++ i)

const double eps = 1e-3;
const double sqrt3 = sqrt(3);

double xy[1505][2];     int delta[1505];

inline double my_abs(const double z) { return z > eps ? z : -z; }

inline bool is_less(const double a[], const double b[]) {
    double diff0 = a[0] - b[0];
    double diff1 = a[1] - b[1];
     if (my_abs(diff0) < eps) {
         if (my_abs(diff1) < eps)
             return false;
         else
             return diff1 < eps;
     }
     return diff0 < eps;
}

double dist(const double a[], const double b[]) {
    return sqrt( (b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1]) );
}

int binary_search(int l, int r, double x, double y) {
    double p[] = {x, y};
    int delta, i;

    delta = 1 << (::delta[r - l]);

    for (i = l; delta; delta /= 2) {
        if (i + delta < r) if (is_less(xy[i + delta], p))
             i += delta;
    }
    if (is_less(xy[i], p)) if (i < r - 1)
        i ++;
    return !is_less(p, xy[i]) && !is_less(xy[i], p);
}

int main(void) {
    ifstream in(iname);
    int n;
    double new_x, new_y, d, a, b, x, y, angle, rsin, rcos;

    in >> n;
    FOR (i, 0, n)
        in >> xy[i][0] >> xy[i][1];
    in.close();

    for (int i = 0; (1 << i) <= n; ++ i)
        delta[1 << i] = i;
    FOR (i, 3, n + 1) if (!delta[i])
        delta[i] = delta[i - 1];

    FOR (i, 0, n) FOR (j, i + 1, n) if (is_less(xy[j], xy[i])) {
        swap(xy[i][0], xy[j][0]);
        swap(xy[i][1], xy[j][1]);
    }

    int res = 0;

    FOR (i, 0, n - 2) FOR (j, i + 1, n - 1) {
        d = dist(xy[i], xy[j]) / 2;
        if (xy[i][0] == xy[j][0]) {
            new_x = d * sqrt3;
            new_y = d;
            res += binary_search(j + 1, n, new_x, new_y);
            new_x = -new_x;
            res += binary_search(j + 1, n, new_x, new_y);
        }
        else {
            angle = atan2(xy[j][1] - xy[i][1], xy[j][0] - xy[i][0]);
            a = xy[i][0], b = xy[i][1];
            x = d, y = d * sqrt3;
            rsin = sin(angle), rcos = cos(angle);
            new_x = x * rcos - y * rsin + a;
            new_y = x * rsin + y * rcos + b;
            res += binary_search(j + 1, n, new_x, new_y);
            new_x += 2 * y * rsin;
            new_y -= 2 * y * rcos;
            res += binary_search(j + 1, n, new_x, new_y);
        }
    }

    ofstream(oname) << res;

    return 0;
}