Cod sursa(job #772646)

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

#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()
{
    ifstream f("triang.in");
    ofstream g("triang.out");

    f >> n;
    for (int i = 1; i <= n; ++i) {
        double j, k;
        f >> 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;
        }

    g << sol;
    
    return 0;
}