Cod sursa(job #767786)

Utilizator doc2177Dorian Croitoru doc2177 Data 14 iulie 2012 21:36:10
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int i,DX,DY,N;
vector<int> horiz,vert;
int main()
{
  freopen("tribute.in","r",stdin);
  freopen("tribute.out","w",stdout);
  cin >> N >> DX >> DY;
  int a,b;
  for (i=0; i!=N; ++i)
    {
      cin >> a >> b;
      horiz.push_back(a); 
      vert.push_back(b); 
    }
  sort(horiz.begin(),horiz.end());
  sort(vert.begin(),vert.end());
  
  int min_h(accumulate(horiz.begin(),horiz.end(),-horiz[0]*horiz.size()));
  int min_v(accumulate(vert.begin(),vert.end(),-vert[0]*vert.size()));
  int h(min_h),v(min_v);
  for (i=horiz[0]; i<=horiz.back()-DX; ++i)
    {
      h+=int(lower_bound(horiz.begin(),horiz.end(),i)-horiz.begin())
        -int(horiz.end()-upper_bound(horiz.begin(),horiz.end(),i));
      if (h<min_h) min_h=h;
    }
  for (i=vert[0]; i<=vert.back()-DY; ++i)
    {
      v+=int(lower_bound(vert.begin(),vert.end(),i)-vert.begin())
        -int(vert.end()-upper_bound(vert.begin(),vert.end(),i));
      if (v<min_v) min_v=v;
    }
  cout << min_h+min_v <<"\n";
  return 0;
}