Cod sursa(job #290903)

Utilizator MariusMarius Stroe Marius Data 28 martie 2009 22:18:03
Problema Triang Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 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];

#define my_abs(z)  ((z) > eps ? (z) : (-(z)))

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

bool equal(const double a[], const double b[]) {
    return my_abs(a[0] - b[0]) < eps && my_abs(a[1] - b[1]) < 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};
    while (l < r) {
        int m = (l + r) / 2;
        if (!is_less(p, xy[m]) && !is_less(xy[m], p))  return 1;
        if (is_less(p, xy[m]))
            r = m - 1;
        else
            l = m + 1;
    }
    return equal(p, xy[r]) ? 1 : 0;
}

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

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

    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]);
        if (xy[i][0] == xy[j][0]) {
            new_x = d * sqrt3 / 2;
            new_y = d / 2;
            res += binary_search(j + 1, n - 1, new_x, new_y);
            new_x = -new_x;
            res += binary_search(j + 1, n - 1, 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 / 2, y = d * sqrt3 / 2;
            new_x = x * cos(angle) - y * sin(angle) + a;
            new_y = x * sin(angle) + y * cos(angle) + b;
            res += binary_search(j + 1, n - 1, new_x, new_y);
            new_x = x * cos(angle) + y * sin(angle) + a;
            new_y = x * sin(angle) - y * cos(angle) + b;
            res += binary_search(j + 1, n - 1, new_x, new_y);
        }
    }

    ofstream(oname) << res;

    return 0;
}