Cod sursa(job #1804697)

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

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 double dist(double x1, double y1, double x2, double y2){
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
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)
            dr = mij - 1;
        else
            st = mij + 1;
    }
    for(int i = dr; i <= n ; ++i){
        if(a[i].x - x > EPS) return 0;
        if(a[i].y - y <= EPS) return 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 xm = (a[i].x + a[j].x) / 2, ym = (a[i].y + a[j].y) / 2;
            double x1 = 0, x2 = 0, y1 = 0, y2 = 0;
            double d = dist(a[i].x , a[i].y, a[j].x, a[j].y);
            double slope = 0;
            if(fabs(a[i].y - a[j].y) < EPS){
                x1 = x2 = xm;
                y1 = ym + sqrt(3.0)*sqrt(d) / 2;
                y2 = ym - sqrt(3.0)*sqrt(d) / 2;
            }else{
                if(fabs(a[j].x - a[i].x) < EPS)
                    slope = 0;
                else
                    slope = -(a[j].x - a[i].x) / (a[j].y - a[i].x);
                x1 = (2 * xm + sqrt(3 * d / (slope * slope + 1))) / 2;
                x2 = (2 * xm - sqrt(3 * d / (slope * slope + 1))) / 2;
                y1 = x1 * slope - slope * xm + ym;
                y2 = x2 * slope - slope * xm + ym;
            }
            if(FIND(x1, y1)) ++NR;
            if(FIND(x2, y2)) ++NR;
        }
    }
    printf("%d", NR / 3);
    return 0;
}