Cod sursa(job #1488010)

Utilizator akaprosAna Kapros akapros Data 17 septembrie 2015 19:29:06
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define e 0.001
#define sinA 0.8660
#define cosA 0.500
#define maxN 1502
using namespace std;
int n, i, j, sol;
struct point
{
    double x;
    double y;
}v[maxN];
int cmp(const point a, const point b)
{
    if (fabs(a.x - b.x) < e)
        return a.y < b.y;
    return a.x < b.x;
}
void read()
{
    freopen("triang.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
}
int bs(point a)
{
    int i = 1, p = 1 << 10;
    while (p)
    {
        if (i + p <= n && v[i + p].x < a.x )
            i += p;
        p /= 2;
    }
    if (v[i].x + e < a.x)
        ++ i;
    if (fabs(v[i].x - a.x) > e)
        return 0;
    p = 1 << 10;
        while (p)
    {
        if (i + p <= n && fabs(v[i + p].x - v[i].x) < e && (v[i + p].y < a.y || fabs(v[i + p].y - a.y) < e))
            i += p;
        p /= 2;
    }

    if ((double) fabs(v[i].y - a.y) < e)
    return 1;
    return 0;
}
void solve()
{
    point p;
    p.x = 0.000;
    p.y = 0.000;
    sort(v + 1, v + n + 1, cmp);
    for (i = 1; i <= n; ++ i)
        for (j = i + 1; j <= n; ++ j)
    {
        p.x = (v[i].x + v[j].x) * cosA + (v[i].y - v[j].y) * sinA;
        p.y = (v[j].x - v[i].x) * sinA + (v[i].y + v[j].y) * cosA;
        sol += bs(p);

        p.x = (v[i].x + v[j].x) * cosA + (v[j].y - v[i].y) * sinA;
        p.y = (v[i].x - v[j].x) * sinA + (v[i].y + v[j].y) * cosA;
        sol += bs(p);
    }
}
void write()
{
    freopen("triang.out", "w", stdout);
    printf("%d\n", sol / 3);
}
int main()
{
    read();
    solve();
    write();
}