Cod sursa(job #1992967)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 22 iunie 2017 00:03:12
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 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;

int n;

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

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 l = (v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y);
           if(v[i].x == v[j].x) {
               y3 = y4 = (v[j].y * v[j].y - v[i].y * v[i].y) / (2 * (v[j].y - v[i].y));
               x3 = sqrt(l - (y3 - v[i].y) * (y3 - v[i].y)) + v[i].x;
               x4 = - sqrt(l - (y3 - v[i].y) * (y3 - v[i].y)) + v[i].x;
           }
           else {
               double a, b;
               a = (v[j].x * v[j].x - v[i].x * v[i].x + v[j].y * v[j].y - v[i].y * v[i].y) / (2 * (v[j].x - v[i].x));
               b = (v[j].y - v[i].y)/(v[j].x - v[i].x);
               double delta = sqrt((v[i].x * b - a * b - v[i].y) * (v[i].x * b - a * b - v[j].y) - (1 + b * b) * (v[i].x * v[i].x + a * a + v[i].y * v[i].y - 2 * v[i].x * a - l));
               y3 = (a * b + v[i].y - v[i].x * b + delta) / (1 + b * b);
               y4 = (a * b + v[i].y - v[i].x * b - delta) / (1 + b * b);
               x3 = a - y3 * b;
               x4 = a - y4 * b;
           }
           ans += check(x3, y3);
           ans += check(x4, y4);
       }
    cout << ans;
    cin.close();
    cout.close();
    return 0;
}