Cod sursa(job #2668148)

Utilizator IacobTudorIacob Tudor IacobTudor Data 4 noiembrie 2020 16:01:51
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("window.in");
ofstream fout("window.out");
int n, dx, dy, x[50005], y[50005];
long long Dst(int pos, int x[], int dx){
    long long ans=0;
    for (int i=1;i<=n;i++){
        if(pos<=x[i]&&x[i]<=pos+dx)continue;
        ans+=min(abs(pos-x[i]), abs(pos+dx-x[i]));
    }
    return ans;
}
long long solve(int x[], int dx){
    int st=0,dr=50000;
    while (st<dr-2){
        int mid1=(2*st+dr)/3;
        int mid2=(st+2*dr)/3;
        long long ans1=Dst(mid1, x, dx);
        long long ans2=Dst(mid2, x, dx);
        if (ans1<ans2)dr=mid2;
        else st=mid1;
    }
    return min(min(Dst(st, x, dx), Dst(st+1, x, dx)), Dst(st+2, x, dx));
}
int main(){
    fin>>n>>dx>>dy;
    for (int i=1;i<=n;i++){
        fin>>x[i]>>y[i];
    }
    long long ans = solve(x, dx) + solve(y, dy);
    fout<<ans<<'\n';
    return 0;
}