Cod sursa(job #1295897)

Utilizator RaduVisanRadu Visan RaduVisan Data 20 decembrie 2014 13:37:40
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 1510;
const double EPS = 1e-3, PI = 3.14159265359;

int N, Ans;
pair<double, double> V[NMAX];

struct Comp
{
    bool operator() (const pair<double, double> &A, const pair<double, double> &B) const
    {
        if(fabs(A.first - B.first) > EPS) return A.first < B.first;
        else return A.second < B.second;
    }
};

bool LessOrEqual(pair<double, double> A, pair<double, double> B)
{
    if(fabs(A.first - B.first) > EPS) return A.first < B.first;
    if(fabs(A.second - B.second) <= EPS) return 1;
    return A.second < B.second;
}

bool BS(pair<double, double> P)
{
    int Left = 1, Right = N, Mid, Ans = -1;
    while(Left <= Right)
    {
        Mid = (Left + Right) / 2;
        if(LessOrEqual(V[Mid], P)) Ans = Mid, Left = Mid + 1;
        else Right = Mid - 1;
    }

    if(Ans != -1 && fabs(V[Ans].first - P.first) < EPS && fabs(V[Ans].second - P.second) < EPS) return 1;
    return 0;
}

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

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
        scanf("%lf %lf", &V[i].first, &V[i].second);

    sort(V + 1, V + N + 1, Comp());

    for(int i = 1; i <= N; ++ i)
        for(int j = i + 1; j <= N; ++ j)
        {
            pair<double, double> Other;
            Other.first = V[i].first + (V[j].first - V[i].first) * cos(PI / 3) - (V[j].second - V[i].second) * sin(PI / 3);
            Other.second = V[i].second + (V[j].first - V[i].first) * sin(PI / 3) + (V[j].second - V[i].second) * cos(PI / 3);

            Ans += BS(Other);

            Other.first = V[i].first + (V[j].first - V[i].first) * cos(-PI / 3) - (V[j].second - V[i].second) * sin(-PI / 3);
            Other.second = V[i].second + (V[j].first - V[i].first) * sin(-PI / 3) + (V[j].second - V[i].second) * cos(-PI / 3);

            Ans += BS(Other);
        }

    printf("%i\n", Ans / 3);
}