Cod sursa(job #1463029)

Utilizator cojocarugabiReality cojocarugabi Data 19 iulie 2015 17:56:06
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
# include <bits/stdc++.h>
# define db long double
# define x first
# define y second
const double pi = 3.14159265359;
const double eps = 1e-3;
using namespace std;
int n;
ifstream fi("triang.in");
ofstream fo("triang.out");
pair < db , db > v[1505];
int cmp(pair < db , db > a,pair < db , db > b)
{
    if (a.x - b.x < -eps) return 0;
    if (a.x - b.x > eps) return 2;
    if (a.y - b.y < -eps) return 0;
    if (a.y - b.y > eps) return 2;
    return 1;
}
bool ok(int p,int u,pair < db , db > d)
{
    int e = 1024;
    --p;
    while (e)
    {
        if (p + e <= n)
            if (cmp(d,v[p + e]) == 2) p += e;
        e >>= 1;
    }
    ++p;
    return (p <= u && cmp(d,v[p]) == 1);
}
int main(void)
{
    fi>>n;
    for (int i = 1;i <= n;++i)
    {
        fi>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+n);
    int ans = 0;
    db cos60 = cos(M_PI / 3);
    db sin60 = sin(M_PI / 3);
    db cos_60 = cos(-M_PI / 3);
    db sin_60 = sin(-M_PI / 3);
    for (int i = 1;i <= n;++i)
        for (int j = i + 1;j <= n;++j)
        {
            pair < db , db > p,d;
            p.x = v[j].x - v[i].x;
            p.y = v[j].y - v[i].y;
            d.x = p.x * cos60 - p.y * sin60;
            d.y = p.x * sin60 + p.y * cos60;
            d.x += v[i].x;d.y += v[i].y;
            ans += ok(1,n,d);
            d.x = p.x * cos_60 - p.y * sin_60;
            d.y = p.x * sin_60 + p.y * cos_60;
            d.x += v[i].x;d.y += v[i].y;
            ans += ok(1,n,d);
        }
    ans /= 3;
    return fo << ans << '\n',0;
}