Cod sursa(job #772639)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 30 iulie 2012 13:15:30
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <cmath>
#include <cstdio>

#include <algorithm>
#include <vector>

using namespace std;

#define x first
#define y second

const double EPS = 1e-3;
const double pi = 3.14159265;
const double c60 = cos(pi / 3);
const double s60 = sin(pi / 3);

int n, sol;
double X, Y;
vector <pair <double, double> > a;

int equal(double a, double b)
{
    if (fabs(a - b) < EPS)
        return 1;
    return 0;
}

int less(double a, double b)
{
    if (a + EPS < b)
        return 1;
    return 0;
}

int cmp(pair <double, double> a, pair <double, double> b)
{
    if(equal(a.x, b.x))
        return less(a.y, b.y);
    return less(a.x, b.x);
}

int exista(int left, int right, double X, double Y)
{
    while (left <= right) {
        int m = left + (right - left) / 2;
        if (equal(X, a[m].x) && equal(Y, a[m].y))
            return 1;
        if (less(a[m].x, X) || (equal(a[m].x, X) && less(a[m].y, Y)))
            left = m + 1;
        else
            right = m - 1;
    }

    return 0;
}

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

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        double j, k;
        scanf("%lf %lf", &j, &k);
        a.push_back(make_pair(j, k));
    }

    sort(a.begin(), a.end(), cmp);

    for (int i = 0; i < n - 2; ++i)
        for (int j = i + 1; j < n - 1; ++j) {
            X = a[i].x + (a[j].x - a[i].x) * c60 - (a[j].y - a[i].y) * s60;
            Y = a[i].y + (a[j].x - a[i].x) * s60 + (a[j].y - a[i].y) * c60;
            if (exista(j + 1, n - 1, X, Y))
                ++sol;

            X = a[i].x + (a[j].x - a[i].x) * c60 - (a[j].y - a[i].y) * (-s60);
            Y = a[i].y + (a[j].x - a[i].x) * (-s60) + (a[j].y - a[i].y) * c60;
            if (exista(j + 1, n - 1, X, Y))
                ++sol;
        }

    printf("%d", sol);
    
    return 0;
}