Cod sursa(job #1291584)

Utilizator OwlreeRobert Badea Owlree Data 12 decembrie 2014 23:16:32
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>

using namespace std;

const double PI = 3.14159265;

double dst(double x, double y) {
  return sqrt(x * x + y * y);
}

pair <double, double> up(pair <double, double> p1, pair <double, double> p2) {

  pair<double, double> p2c = p2;
  pair<double, double> p2r = {0, 0};

  p2.first -= p1.first; p2.second -= p1.second;

  p2r.first  = p2.first * cos(45.0 * PI / 180) - p2.second * sin(45.0 * PI / 180);
  p2r.second = p2.first * sin(45.0 * PI / 180) + p2.second * cos(45.0 * PI / 180);

  double d  = dst(p2r.first, p2r.second);
  double nd = dst(p1.first - p2c.first, p1.second - p2c.second) / sqrt(2);

  p2r.first  /= d;
  p2r.second /= d;

  p2r.first  *= nd;
  p2r.second *= nd;

  p2r.first += p1.first; p2r.second += p1.second;

  return p2r;
}

pair <double, double> down(pair <double, double> p1, pair <double, double> p2) {

  pair<double, double> p2c = p2;
  pair<double, double> p2r = {0, 0};

  p2.first -= p1.first; p2.second -= p1.second;

  p2r.first  = p2.first * cos( - 45.0 * PI / 180) - p2.second * sin( - 45.0 * PI / 180);
  p2r.second = p2.first * sin( - 45.0 * PI / 180) + p2.second * cos( - 45.0 * PI / 180);

  double d  = dst(p2r.first, p2r.second);
  double nd = dst(p1.first - p2c.first, p1.second - p2c.second) / sqrt(2);

  p2r.first  /= d;
  p2r.second /= d;

  p2r.first  *= nd;
  p2r.second *= nd;

  p2r.first += p1.first; p2r.second += p1.second;

  return p2r;
}

int main() {

  ifstream in("patrate3.in");
  ofstream out("patrate3.out");

  int N;
  in >> N;
  vector <pair <double, double> > v(N);

  for (int i = 0; i < N; ++i) {
    in >> v[i].first >> v[i].second;
  }

  sort(v.begin(), v.end());

  int tot = 0;

  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {

      if (v[j].second - v[i].second < 0) {
        continue;
      }

      pair <double, double> u, d;
      u = up(v[i], v[j]);
      d = down(v[i], v[j]);
      u.first = ((double)round(u.first * 10000)) / (double)10000.0;
      u.second = ((double)round(u.second * 10000)) / (double)10000.0;
      d.first = ((double)round(d.first * 10000)) / (double)10000.0;
      d.second = ((double)round(d.second * 10000)) / (double)10000.0;

      if (binary_search(v.begin(), v.end(), u) && binary_search(v.begin(), v.end(), d)) {
        tot += 1;
      }
    }
  }

  out << tot << "\n";

  in.close();
  out.close();

  return 0;

}