Cod sursa(job #1291567)

Utilizator OwlreeRobert Badea Owlree Data 12 decembrie 2014 22:47:53
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 3.14 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;
  unordered_map <int, vector < pair<double, double> > > mp;
  vector < pair <double, double> > all(N);

  for (int i; i < N; ++i) {
    double x, y;
    in >> x >> y;
    int d = (int)dst(x, y);
    mp[d].push_back({x, y});
    all[i].first = x;
    all[i].second = y;
  }

  sort(all.begin(), all.end());
  int tot = 0;

  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      pair <double, double> u, d;

      u = up(all[i], all[j]);
      d = down(all[i], all[j]);

      // cout << setw(5) << all[i].first << ", " << setw(5) << all[i].second << " | ";
      // cout << setw(5) << all[j].first << ", " << setw(5) << all[j].second << " | ";
      // cout << setw(5) << u.first << ", " << setw(5) << u.second << " | ";
      // cout << setw(5) << d.first << ", " << setw(5) << d.second << " | ";

      // search for u and d
      double dstu = dst(u.first, u.second);
      double dstd = dst(d.first, d.second);

      vector <pair <double, double> > uv = mp[(int)dstu];
      vector <pair <double, double> > dv = mp[(int)dstd];

      bool foundu = false;

      for (int ii = 0; ii < (int)uv.size(); ++ii) {
        if (abs(uv[ii].first - u.first) < 0.00001 && 
            abs(uv[ii].second - u.second) < 0.00001) {
          foundu = true;
          break;
        }
      }

      if (foundu) {
        for (int ii = 0; ii < (int)uv.size(); ++ii) {
          if (abs(dv[ii].first - d.first) < 0.00001 && 
              abs(dv[ii].second - d.second) < 0.00001) {
            tot++;
            // cout << "YES!!";
            break;
          }
        }
      }
      // cout << "\n";
    }
  }

  out << tot / 2 << "\n";

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

  return 0;

}