Cod sursa(job #1291627)

Utilizator OwlreeRobert Badea Owlree Data 13 decembrie 2014 00:36:34
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.36 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;
 
}