Cod sursa(job #2271796)

Utilizator alexradu04Radu Alexandru alexradu04 Data 29 octombrie 2018 11:19:24
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define all(x) (x).begin(), (x).end()
#define x first
#define y second

const double kEps = 1e-4;
const double kPi = acos(-1.0);
const double kSin60 = sin(60.0 * kPi / 180.0);
const double kCos60 = cos(60.0 * kPi / 180.0);

int n;
vector<pdd> p;

bool eq(double a, double b) {
  return fabs(a - b) < kEps;
}

pdd rotatePoint(const pdd& p1, const pdd& p2) {
  return {
    kCos60 * (p1.x - p2.x) - kSin60 * (p1.y - p2.y) + p2.x,
    kSin60 * (p1.x - p2.x) + kCos60 * (p1.y - p2.y) + p2.y
  };
}

bool BinarySearch(const pdd& third) {
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    int mi = (l + r) / 2;
    if (eq(p[mi].x, third.x) && eq(p[mi].y, third.y)) {
      return 1;
    }

    if (eq(p[mi].x, third.x)) {
      if (third.y < p[mi].y) {
        r = mi - 1;
      } else {
        l = mi + 1;
      }
    } else if (third.x < p[mi].x) {
      r = mi - 1;
    } else {
      l = mi + 1;
    }
  }

  return 0;
}

int main() {
  cin.sync_with_stdio(false);

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

  cin >> n;

  p.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i].x >> p[i].y;
  }

  sort(all(p));

  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j) {
        pdd third = rotatePoint(p[i], p[j]);
        ans += BinarySearch(third);
      }
    }
  }

  cout << ans / 3 << '\n';

  return 0;
}