Cod sursa(job #1992969)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 22 iunie 2017 00:18:46
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define MAXN 1500

std::pair <double, double> v[MAXN + 1];

const double eps = 1e-3;
const double sn = sqrt((double) 3.0 / 4.0);
const double cs = 0.5;

int n;

inline bool equal(double a, double b) {
    return std::abs(a - b) <= eps;
}

inline bool check(int p, double x, double y) {
     int rez = p;
     for(int pas = 1 << 10; pas; pas >>= 1)
        if(rez + pas <= n && (v[rez + pas].x < x || (equal(v[rez + pas].x, x) && (v[rez + pas].y < y || equal(v[rez + pas].y, y)))))
          rez += pas;
     if(rez == p)
         return 0;
     return (equal(x, v[rez].x) && equal(y, v[rez].y));
}

int main() {
    std::ifstream cin("triang.in");
    std::ofstream cout("triang.out");
    int i, j;
    cin >> n;
    for(i = 1; i <= n; i++)
       cin >> v[i].x >> v[i].y;
    std::sort(v + 1, v + n + 1);
    int ans = 0;
    for(i = 1; i < n; i++)
       for(j = i + 1; j <= n; j++) {
           double x3, y3, x4, y4;
           double x = v[j].x - v[i].x, y = v[j].y - v[i].y;
           x3 = v[i].x + x * cs - y * sn;
           y3 = v[i].y + x * sn + y * cs;
           ans += check(j, x3, y3);
           x4 = v[i].x + x * cs + y * sn;
           y4 = v[i].y - x * sn + y * cs;
           ans += check(j, x4, y4);
       }
    cout << ans;
    cin.close();
    cout.close();
    return 0;
}