Cod sursa(job #1521171)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 9 noiembrie 2015 23:09:48
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int DIM  = (1<<11);
const double  PI  = M_PI;
const double sin1 = sin  (+PI / 3);
const double sin2 = sin  (-PI / 3);
const double cos1 = cos  (+PI / 3);
const double cos2 = cos  (-PI / 3);
const double EPS  =     0.001;

struct point {
    double x;
    double y;
};

point Point[DIM]; int N;

bool cmp (const point A, const point B)
{
    if (fabs(A.x - B.x) < EPS)
        return A.y < B.y;
    else
        return A.x < B.x;
}

bool getPoint (point X)
{
    int left = 1, right = N, middle;

    while (left <= right)
    {
        middle = (left + ((right - left) >> 1));

        if (fabs (X.x - Point[middle].x) < EPS && fabs (X.y - Point[middle].y) < EPS)
            return 1;

        if (Point[middle].x < X.x)
            left = middle + 1;
        else
            right = middle - 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 ++)
    {
        scanf ("%lf", &Point[i].x);
        scanf ("%lf", &Point[i].y);
    }

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

    int answer = 0;
    for (int i = 1; i < N; i ++)
    {
        for (int j = i + 1; j <= N; j ++)
        {
            point A, B, aux, C;

            A = Point[i];
            B = Point[j];
            aux.x = B.x - A.x;
            aux.y = B.y - A.y;

            C.x = aux.x * cos1 - aux.y * sin1;
            C.y = aux.x * sin1 - aux.y * cos1;
            C.x += A.x; C.y += A.y;

            if (getPoint(C))
                answer ++;

            C.x = aux.x * cos2 - aux.y * sin2;
            C.y = aux.x * sin2 - aux.y * cos2;
            C.x += A.x; C.y += A.y;

            if (getPoint(C))
                answer ++;

        }
    }

    // A-B cauta C; A-C cauta B & B-C cauta A
    printf ("%d\n", answer);

    fclose (stdin );
    fclose (stdout);

    return 0;
}