Cod sursa(job #1069295)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 29 decembrie 2013 19:05:30
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;


int n;
vector <pair<int, int> > points;

void get_data(){
  ifstream in("patrate3.in");
  in>>n;
  cout<<n<<"\n";
  for (int i = 1; i <= n; ++i){
    double x, y;
    in>>x>>y;

    int xx = (int) (x * 10000);
    int yy = (int) ( y * 10000);
    cout<<xx<<" "<<yy<<" ";
    pair<int, int> v = make_pair(xx,yy);
    points.push_back(v);
    cout<<i<<"\n";
  }
  cout<<"it's over";
  in.close();
}

bool cmp( pair<int, int> a, pair<int, int> b){
  if (a.first < b.first) return true;
  if (a.first == b.first) return a.second < b.second;
  else return false;
}

bool bin_search(pair <int, int> x) {
  int step = 1 << 9;
  int poz;
  for (int i = 0; step; step >= 1)
    if (i+step <= n && points[i+step] <= x) {
      i+= step;
      poz = i;
    }
  return points[poz] == x;
}

int solve(){
  int sol = 0;
  sort(points.begin(), points.end(), cmp);
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      pair<int, int> x,y;
      int mijx = (points[i].first + points[j].first);
      int mijy = (points[i].second + points[j].second);
      int dx = abs(mijx - points[i].first);
      int dy = abs(mijy - points[i].second);
      if (points[i].second < points[j].second)  {
        x.first = mijx + dy;
        x.second = mijy - dx;
        y.first = mijx - dy;
        y.second = mijy + dx;
      }else {
        x.first = mijx - dy;
        x.second = mijy - dx;
        y.first = mijx + dy;
        y.second = mijy + dx;
      }
      if  (bin_search(x) && bin_search(y)) sol++;
}
return sol/2;
}

int main(){
  cout<<"mata!!!";
  get_data();
  ofstream out("patrate3.out");
  out<<solve();
  out.close();
  return 0;
}