Cod sursa(job #2592150)

Utilizator lucametehauDart Monkey lucametehau Data 1 aprilie 2020 12:13:45
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define ld long double

using namespace std;

ifstream cin ("triang.in");
ofstream cout ("triang.out");

const ld EPS = 1e-6;

int n, ans;

pair <ld, ld> v[1505];

bool comp(pair <ld, ld> a, pair <ld, ld> b) {
  if(abs(b.first - a.first) <= EPS)
    return (b.second - a.second >= -EPS);
  return (b.first - a.first > -EPS);
}

bool find(ld x, ld y) {
  int st = 1, dr = n, mid;
  while(st <= dr) {
    mid = (st + dr) >> 1;
    if(comp(v[mid], make_pair(x, y)))
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return (x - v[dr].first <= EPS && y - v[dr].second <= EPS);
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i].first >> v[i].second;
  sort(v + 1, v + n + 1, comp);
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      ld x = (v[i].first + v[j].first) / 2 - sqrtf(3) / 2 * (v[j].second - v[i].second), y = (v[i].second + v[j].second) / 2 + sqrtf(3) / 2 * (v[j].first - v[i].first);
      ans += find(x, y);
      x = (v[i].first + v[j].first) / 2 + sqrtf(3) / 2 * (v[j].second - v[i].second), y = (v[i].second + v[j].second) / 2 - sqrtf(3) / 2 * (v[j].first - v[i].first);
      ans += find(x, y);
    }
  }
  cout << ans / 3;
  return 0;
}