Cod sursa(job #1521180)

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

/* Mai jos sunt cateva din formulele nestiute ale matematicii
    care nu vor fi demonstrate vreodata datorita complexitatii
    lor de intelegere, cat si prin faptul ca fiecare din
    else este in sinea sa un paradox :D - Citat din mate.    */

const double  PI = M_PI;
const double EPS = 0.001;
const    int DIM = (1<<11);
const double SIN = sin (PI / 3);
const double COS = cos (PI / 3);

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 start, int finish)
{
    int left = start, right = finish, 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 - 2; i ++)
    {
        for (int j = i + 1; j < N; j ++)
        {
            point A, B, C;

            A = Point[i];
            B = Point[j];

            C.x = (A.x + B.x) * COS + (A.y - B.y) * SIN;
            C.y = (B.x - A.x) * SIN + (A.y + B.y) * COS;

            if (getPoint(C, j + 1, N))
                answer ++;

            C.x = (A.x + B.x) * COS + (B.y - A.y) * SIN;
            C.y = (A.x - B.x) * SIN + (A.y + B.y) * COS;

            if (getPoint(C, j + 1, N))
                answer ++;

        }
    }

    printf ("%d\n", answer);

    fclose (stdin );
    fclose (stdout);

    return 0;
}