Cod sursa(job #826807)

Utilizator Teodor94Teodor Plop Teodor94 Data 1 decembrie 2012 11:46:24
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define x first
#define y second
typedef pair<double, double> point;

const int N = 1502;
const double EPS = 0.0001;

int n;
point v[N];

void read() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);
}

int binary_search(int begin, point a) {
    int i, pas = 1 << 10;

    for (i = begin; pas; pas >>= 1)
        if (i + pas <= n && (v[i + pas].x <= a.x + EPS || (abs(v[i + pas].x - a.x) <= EPS && v[i + pas].y <= a.y + EPS)))
            i += pas;

    if (abs(v[i].x - a.x) <= EPS && abs(v[i].y - a.y) <= EPS)
        return 1;

    return 0;
}

void solve() {
    sort(v + 1, v + n + 1);
    
    int res = 0;

    for (int i = 1; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j) {
            point third_point;
            double plus_x = (v[j].x - v[i].x) / 2.0, plus_y = (v[j].y - v[i].y) / 2.0, sq = sqrt(3.0);

            third_point.x = v[i].x + plus_x + (plus_y * sq);
            third_point.y = v[i].y + plus_y - (plus_x * sq);

            res += binary_search(j + 1, third_point);

            third_point.x = v[i].x + plus_x - (plus_y * sq);
            third_point.y = v[i].y + plus_y + (plus_x * sq);

            res += binary_search(j + 1, third_point);
        }

    printf("%d\n", res);
}

int main() {
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);

    read();

    solve();
}