Cod sursa(job #1248595)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 25 octombrie 2014 16:36:55
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define EPS 1e-5
#define APPROX(a, b) (abs((a) - (b)) <= EPS)

bool findp(std::vector<std::pair<double, double> >& v,
           std::pair<double, double> p) {
  int li = 0, lf = v.size() - 1;
  while (li <= lf) {
    int m = (li + lf) / 2;
    if (APPROX(p.first, v[m].first) &&
        APPROX(p.second, v[m].second)) {
      return true;
    } else if (APPROX(p.first, v[m].first)) {
      if (v[m].second < p.second) {
        li = m + 1;
      } else {
        lf = m - 1;
      }
    } else {
      if (v[m].first < p.first) {
        li = m + 1;
      } else {
        lf = m - 1;
      }
    }
  }

  return false;
}

int main()
{
  std::ifstream in("patrate3.in");
  std::ofstream out("patrate3.out");

  int n;
  in >> n;
  std::vector<std::pair<double, double> > v;
  for (int i = 0; i < n; ++i) {
    std::pair<double, double> p;
    in >> p.first >> p.second;
    v.push_back(p);
  }

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

  int sol = 0;
  for (int i = 0; i < v.size(); ++i) {
    for (int j = i + 1; j < v.size(); ++j) {
      if (v[j].second >= v[i].second) {
        double d = v[j].second - v[i].second;
        double D = v[j].first - v[i].first;
        if (findp(v, std::make_pair(v[i].first - d, v[i].second + D)) &&
            findp(v, std::make_pair(v[j].first - d, v[j].second + D))) {
          sol++;
        }
      }
    }
  }

  out << sol << std::endl;

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

  return 0;
}