Cod sursa(job #1096145)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 1 februarie 2014 16:44:10
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

ifstream fin("triang.in");
ofstream fout("triang.out");

const int Nmax = 1550;
const double EPS = 1e-7;
const double sin60 = sin(M_PI / 3.00);
const double cos60 = cos(M_PI / 3.00);

struct pct{
    double x, y;
}P[Nmax];

int N, LG, sol;

bool cmp(const pct &a, const pct &b)
{
    if(fabs(a.x - b.x) < EPS)
    {
        if(fabs(a.y - b.y) < EPS) return 0;
        return a.y < b.y;
    }
    return a.x < b.x;
}

pct TVarf(pct a, pct b)
{
    pct c;
    double dx = b.x - a.x, dy = b.y - a.y;
    c.x = a.x + dx * cos60 - dy * sin60;
    c.y = a.y + dx * sin60 + dy * cos60;
    return c;
}

bool OK(const pct a, const pct b)
{
    if(fabs(a.x - b.x) < EPS)
    {
        if(fabs(a.y - b.y)) return 1;
        return a.y < b.y;
    }
    return a.x < b.x;
}

bool CB(pct A)
{
    int i, lg;
    for(i = 0, lg = LG; lg; lg >>= 1)
        if(i + lg <= N && OK(P[i + lg], A))
            i += lg;
    if(fabs(P[i].x - A.x) < EPS && fabs(P[i].y - A.y) < EPS)
        return 1;
    return 0;
}

int main()
{
    fin >> N;
    for(LG = 1; LG <= N; LG <<= 1);

    for(int i = 1; i <= N; i++)
        fin >> P[i].x >> P[i].y;

    sort(P + 1, P + N + 1, cmp);

    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++)
        {
            pct A = TVarf(P[i], P[j]), B = TVarf(P[j], P[i]);
            if(CB(A)) sol++;
            if(CB(B)) sol++;
        }
    fout << sol / 3;
    return 0;
}