Cod sursa(job #2641734)

Utilizator euyoTukanul euyo Data 12 august 2020 16:41:57
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream fin( "tribute.in" );
ofstream fout( "tribute.out" );

const int MaxN = 50002;

int x[MaxN], y[MaxN];
int xs[MaxN], ys[MaxN];
int maxx[MaxN], maxy[MaxN];
	
int cautbin( int v[], int e, int n, int ind ) {
  int step;
 
  for ( step = 1; step <= n; step <<= 1 );
  for ( ; step > 0; step >>= 1 ) {
    if ( ind + step <= n ) {
      if ( v[ind + step] <= e ) {
        ind += step;
      }
    }
  }
  return ind;
}

int main() {
  int n, dx, dy, i, px, py, p;
  
  fin >> n >> dx >> dy;
  for ( i = 1; i <= n; ++i ) {
	fin >> x[i] >> y[i];
  }
  sort( x + 1, x + n + 1 );
  sort( y + 1, y + n + 1 );
  for ( i = 1; i <= n; ++i ) {
    xs[i] = xs[i - 1] + x[i]; 
    ys[i] = ys[i - 1] + y[i];
  }
  long long sol = 2500000000;
  for ( i = 1; i <= n; ++i ) {
    px = cautbin( x, x[i] + dx - 1, n, i );
	py = cautbin( y, y[i] + dy - 1, n, i );
    p = min( px, py );
    if ( !( x[p] <= x[i] + dx - 1 && y[p] <= y[i] + dy - 1 ) ) {
      p = i;
	}
	int r = ((i - 1) * x[i] - xs[i - 1] + xs[n] - xs[p] - (n - p) * x[i]) + ((i - 1) * y[i - 1] - ys[i - 1] + ys[n] - ys[p] - (n - p) * y[i]); 
	//printf( "%d\n", r );
    if ( sol > r ) {
      sol = r;
	}
  }
  fout << sol;
  fin.close();
  fout.close();
  return 0;
}