Cod sursa(job #1107980)

Utilizator poptibiPop Tiberiu poptibi Data 15 februarie 2014 12:12:29
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <cstdlib>
#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> P[NMAX];

bool BS(pair<double, double> X)
{
    int Left = 1, Right = N, Mid;
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;

        if(fabs(P[Mid].first - X.first) < EPS && fabs(P[Mid].second - X.second) < EPS) return 1;
        if(P[Mid].first < X.first || (fabs(P[Mid].first - X.first) < EPS && P[Mid].second < X.second)) Left = Mid + 1;
        else Right = Mid - 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", &P[i].first, &P[i].second);

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

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

            Ans += BS(NewP);

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

            Ans += BS(NewP);
        }

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