Cod sursa(job #767811)

Utilizator doc2177Dorian Croitoru doc2177 Data 14 iulie 2012 22:33:44
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int i,DX,DY,N,a,b;
vector<int> horiz,vert;
int main()
{
  freopen("tribute.in","r",stdin);
  freopen("tribute.out","w",stdout);
  cin >> N >> DX >> DY;
  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());
  a=(horiz.end()-upper_bound(horiz.begin(),horiz.end(),DX))*DX;
  int min_h(accumulate(upper_bound(horiz.begin(),horiz.end(),DX),horiz.end(),-a));
  a=(vert.end()-upper_bound(vert.begin(),vert.end(),DY))*DY;
  int min_v(accumulate(upper_bound(vert.begin(),vert.end(),DY),vert.end(),-a));
  int h_min(horiz[0]),v_min(vert[0]);
  int h(min_h),v(min_v);
  for (i=horiz[0]+1; 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+DX-1));
      if (h<min_h) { min_h=h; h_min=i;}
    }
  for (i=vert[0]+1; 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+DY-1));
      if (v<min_v) { min_v=v; v_min=i;}
    }
  cout << min_h+min_v << "\n";
  return 0;
}