Cod sursa(job #1804706)

Utilizator giotoPopescu Ioan gioto Data 12 noiembrie 2016 21:39:47
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define EPS 0.001
using namespace std;

double Pi = acos(-1.0), eps = 0.001;
double c60 = cos(60 * Pi / 180.0), s60 = sin(60 * Pi /180.0),x,y;
int NR, n;
struct Punctulet{
    double x, y;
}a[1501];

inline bool cmp(Punctulet x, Punctulet y){
    if(x.x != y.x) return x.x < y.x;
    return x.y < y.y;
}
inline bool FIND(double x, double y){
    int st = 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij].x - x <= EPS && a[mij].x - x >= -EPS && a[mij].y - y <= EPS && a[mij].y - y >= -EPS)
            return 1;
        if(a[mij].x < x) st = mij + 1;
            else dr = mij  - 1;
    }
    return 0;
}
int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%lf%lf", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i < n ; ++i){
        for(int j = i + 1; j <= n ; ++j){
            double x = c60 * (a[j].x + a[i].x) + s60 * (a[j].y - a[i].y);
            double y = s60 * (a[i].x - a[j].x) + c60 * (a[j].y + a[i].y);
            if(FIND(x, y)) ++NR;
            x = c60 * (a[j].x + a[i].x) + s60 * (a[i].y - a[j].y);
            y = s60 * (a[j].x - a[i].x) + c60 * (a[j].y + a[i].y);
            if(FIND(x, y)) ++NR;
        }
    }
    printf("%d", NR / 3);
    return 0;
}