PROG-1139: อาคารเรียน (campus)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli INF = 2e18;
int n;
lli X[500010], Y[500010], num[500010];

lli DistanceX(lli cur){
    lli sum = 0;
    for(int i = 1; i <= n; i++){
        sum += abs((lli)(X[i] - cur) * num[i]);
    }
    return sum;
}

lli DistanceY(lli cur){
    lli sum = 0;
    for(int i = 1; i <= n; i++){
        sum += abs((lli)(Y[i] - cur) * num[i]);
    }
    return sum;
}

int main(){

    scanf("%d", &n);

    lli xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld", &X[i], &Y[i]);
        scanf("%lld", &num[i]);
        xmin = min(xmin, X[i]);
        xmax = max(xmax, X[i]);
        ymin = min(ymin, Y[i]);
        ymax = max(ymax, Y[i]);
    }

    lli l = xmin, r = xmax;
    lli mnx = INF;
    while(l <= r){
        lli mid = (l + r) / 2;
        lli DisRight = DistanceX(mid + 1);
        lli DisLeft = DistanceX(mid - 1);
        if(DisLeft < DisRight){
            r = mid - 1;
            mnx = min(mnx, DisLeft);
        }
        else{
            l = mid + 1;
            mnx = min(mnx, DisRight);
        }
    }

    l = ymin, r = ymax;
    lli mny = INF;
    while(l <= r){
        lli mid = (l + r) / 2;
        lli DisRight = DistanceY(mid + 1);
        lli DisLeft = DistanceY(mid - 1);
        if(DisLeft < DisRight){
            r = mid - 1;
            mny = min(mny, DisLeft);
        }
        else{
            l = mid + 1;
            mny = min(mny, DisRight);
        }
    }

    printf("%lld", mnx + mny);

    return 0;
}