Cod sursa(job #2027843)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 26 septembrie 2017 19:20:43
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int nmax = 1500;
const double pi = acos(-1);
const double eps = 1.e-3;

struct Point{
    double x, y;
} v[1 + nmax];

bool cmp(Point a, Point b) {
    if(fabs(a.x - b.x) < eps) {
        return a.y - b.y <= -eps;
    }
    return a.x - b.x <= -eps;
}

bool gasit(Point val, int st, int dr) {
    while(st <= dr) {
        int med = (st + dr) / 2;
        if(fabs(val.x - v[med].x) < eps && fabs(val.y - v[med].y) < eps) {
            return 1;
        }
        if(fabs(val.x - v[med].x) < eps) {
            if(val.y - v[med].y >= eps) {
                st = med + 1;
            } else {
                dr = med - 1;
            }
        } else {
            if(val.x - v[med].x >= eps) {
                st = med + 1;
            } else {
                dr = med - 1;
            }
        }
    }
    return 0;
}

int main() {
    freopen("triang.in", "r", stdin);
    freopen("triang.out", "w", stdout);

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        v[i].x = x;
        v[i].y = y;
    }

    sort(v + 1, v + n + 1, cmp);

    int rasp = 0;
    double cos60 = cos(pi/3), cos300 = cos(5 * pi / 3), sin60 = sin(pi / 3), sin300 = sin(5 * pi / 3);
    for(int i = 1; i <= n; ++ i) {
        for(int j = i + 1; j <= n; ++ j) {
            Point aux;
            aux.x = (v[j].x - v[i].x) * cos60 + (v[j].y - v[i].y) * sin60 + v[i].x;
            aux.y = (v[j].y - v[i].y) * cos60 - (v[j].x - v[i].x) * sin60 + v[i].y;
            rasp += gasit(aux, 1, n);
            aux.x = (v[j].x - v[i].x) * cos300 + (v[j].y - v[i].y) * sin300 + v[i].x;
            aux.y = (v[j].y - v[i].y) * cos300 - (v[j].x - v[i].x) * sin300 + v[i].y;
            rasp += gasit(aux, 1, n);
        }
    }

    printf("%d\n", rasp / 3);

    return 0;
}