Cod sursa(job #1458819)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 8 iulie 2015 15:28:49
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

#define PDD pair < double , double >

#define X first
#define Y second

using namespace std;

const double eps = 1e-3;
const int Nmax = 1510;

int n , i , j , ans;
vector < PDD > punct;

int compare(double a , double b)
{
    if (a + eps < b) return -1;
    if (b + eps < a) return 1;
    return 0;
}

double lenght(PDD p , PDD q)
{
    return ( sqrt((p.X-q.X)*(p.X-q.X) + (p.Y-q.Y)*(p.Y-q.Y)) );
}

bool Binary_Search(PDD p , int i)
{
    int step;

    for (step = 1; step < n; step <<= 1);

    for (; step; step >>= 1)
        if (i + step <= n &&
            (compare(punct[i+step].X , p.X) < 0 || (!compare(punct[i+step].X , p.X) && compare(punct[i+step].Y , p.Y) < 0)))
                i += step;

    i++; if (i == n + 1) return false;

    return (!compare(punct[i].X , p.X) && !compare(punct[i].Y , p.Y));
}

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

    scanf("%d", &n);

    punct = vector < PDD > (n + 1);
    for (i = 1; i <= n; ++i)
        scanf("%lf %lf", &punct[i].X, &punct[i].Y);

    sort(punct.begin() + 1 , punct.end());

    for (i = 1; i < n; ++i)
        for (j = i + 1; j <= n; ++j)
        {
            double R = lenght(punct[i] , punct[j]);

            double sinX = (punct[j].Y - punct[i].Y) / R; double cosX = (punct[j].X - punct[i].X) / R;
            double sin60 = sqrt(3) / 2; double cos60 = 0.5;

            double cos_sum = cosX * cos60 - sinX * sin60; double cos_dif = cosX * cos60 + sinX * sin60;
            double sin_sum = sinX * cos60 + sin60 * cosX; double sin_dif = sinX * cos60 - sin60 * cosX;

            PDD point0 = {cos_sum*R+punct[i].X , sin_sum*R+punct[i].Y};

            ans += Binary_Search(point0 , j);

            point0 = {cos_dif*R+punct[i].X , sin_dif*R+punct[i].Y};

            ans += Binary_Search(point0 , j);
        }

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

    return 0;
}