Cod sursa(job #166154)

Utilizator filipbFilip Cristian Buruiana filipb Data 27 martie 2008 15:29:16
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define PDD pair<double, double>
#define EPS 1e-3
#define x first
#define y second

double CT = 0.5 * sqrt(3);
int N, cnt;
PDD v[2048];

inline int compare(const PDD &m, double xx, double yy)
{
    if (m.x + EPS < xx) return -1;
    if (xx + EPS < m.x) return +1;
    if (m.y + EPS < yy) return -1;
    if (yy + EPS < m.y) return +1;
    return 0;
}

int BS(double xx, double yy)
{
    int l, r, m, ok;

    for (l = 1, r = N; l <= r; )
    {
        m = (l + r) / 2;
        ok = compare(v[m], xx, yy);
        if (ok < 0) l = m+1;
        else if (ok > 0) r = m-1;
        else return 1;
    }
    return 0;
}

int main(void)
{
    int i, j;
    double x3, y3;
    
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    sort(v+1, v+N+1);

    for (i = 1; i <= N; ++i)
        for (j = i+1; j <= N; ++j)
        {
            x3 = v[i].x + (v[j].x-v[i].x) * 0.5 - (v[j].y-v[i].y) * CT;
            y3 = v[i].y + (v[j].x-v[i].x) * CT + (v[j].y-v[i].y) * 0.5;
            if (BS(x3, y3))
                ++cnt;

            x3 = v[i].x + (v[j].x-v[i].x) * 0.5 + (v[j].y-v[i].y) * CT;
            y3 = v[i].y - (v[j].x-v[i].x) * CT + (v[j].y-v[i].y) * 0.5;
            if (BS(x3, y3))
                ++cnt;
        }

    printf("%d\n", cnt/3);

    return 0;
}