Cod sursa(job #1570257)

Utilizator LucianTLucian Trepteanu LucianT Data 16 ianuarie 2016 12:03:26
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>
#define abs(x) ((x)<0 ? (-x):(x))
#define sin60 0.8660254
#define cos60 0.5000000
#define EPS 0.001
#define maxN 1510
using namespace std;
struct punct
{
    double x, y;
};
punct v[maxN], pct;
long long sol;
int n, i, j;
bool cmp(punct a, punct b)
{
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool cb(int st, int dr, double x, double y)
{
    int mij;
    while(st <= dr)
    {
        mij = (st+dr)>>1;
        if(abs(x-v[mij].x) < EPS && abs(y-v[mij].y) < EPS) return true;
        else if(v[mij].x < x) st = mij+1;
        else dr = mij-1;
    }
    return false;
}
int main()
{
    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, cmp);
    for(i = 1; i < n-1; i++)
        for(j = i+1; j <= n-1; j++)
    {
        pct.x = (v[j].x+v[i].x)*cos60 + (v[j].y+v[i].y)*sin60;
        pct.y = (v[j].x-v[i].x)*sin60 + (v[j].y-v[i].y)*cos60;
        sol += (int)cb(j+1, n, pct.x, pct.y);
        pct.x = (v[i].x+v[j].x)*cos60 + (v[j].y-v[i].y)*sin60;
        pct.y = (v[i].x-v[j].x)*sin60 + (v[j].y+v[i].y)*cos60;
        sol += (int)cb(j+1, n, pct.x, pct.y);
    }
    printf("%lld", sol);
    return 0;
}