Cod sursa(job #2890618)

Utilizator mateicosCostescu Matei mateicos Data 16 aprilie 2022 04:49:52
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define EPS 0.0001
#define PI 3.14159265

using namespace std;

struct P{
    double x, y;
}v[1505];

int cmp(P x, P y){
    if(abs(x.x - y.x) < EPS)
        return  x.y < y.y;
    return x.x < y.x ;
}

P third_point(P a, P b, double ang){
    double dx, dy, val;
    dx = a.x - b.x;
    dy = a.y - b.y;
    P nw;
    val = PI / 180.;
    nw.x = b.x + dx * cos(ang * val) + dy * sin(ang * val);
    nw.y = b.y + dx * sin((-ang) * val) + dy * cos(ang * val);
    return nw;
}

int bs(int st, int dr, P k){
    int med;
    while(st <= dr){
        med = (st + dr) / 2;
        if(abs(v[med].x - k.x) < EPS){
            if(abs(v[med].y - k.y) < EPS)
                return 1;
            if(v[med].y < k.y){
                st = med + 1;
            }
            else
                dr = med - 1;
        }
        else
        if(v[med].x < k.x)
            st = med + 1;
        else
            dr = med - 1;
    }
    return 0;
}

int main()
{
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);
    int n, i, j, nr;
    scanf("%d", &n);
    for(i = 0;i < n;i++){
        scanf("%lf%lf", &v[i].x, &v[i].y);
    }
    sort(v, v + n, cmp);
    nr = 0;
    for(i = 0;i < n;i++){
        for(j = i + 1;j < n;j++){
            nr += bs(j + 1, n - 1, third_point(v[i], v[j], 60));
            nr += bs(j + 1, n - 1, third_point(v[i], v[j], -60));
        }
    }
    printf("%d", nr);
    return 0;
}