Advertisement
YEZAELP

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

Jan 11th, 2021
145
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 2e18;
  6. int n;
  7. lli X[500010], Y[500010], num[500010];
  8.  
  9. lli DistanceX(lli cur){
  10.     lli sum = 0;
  11.     for(int i = 1; i <= n; i++){
  12.         sum += abs((lli)(X[i] - cur) * num[i]);
  13.     }
  14.     return sum;
  15. }
  16.  
  17. lli DistanceY(lli cur){
  18.     lli sum = 0;
  19.     for(int i = 1; i <= n; i++){
  20.         sum += abs((lli)(Y[i] - cur) * num[i]);
  21.     }
  22.     return sum;
  23. }
  24.  
  25. int main(){
  26.  
  27.     scanf("%d", &n);
  28.  
  29.     lli xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
  30.     for(int i = 1; i <= n; i++){
  31.         scanf("%lld%lld", &X[i], &Y[i]);
  32.         scanf("%lld", &num[i]);
  33.         xmin = min(xmin, X[i]);
  34.         xmax = max(xmax, X[i]);
  35.         ymin = min(ymin, Y[i]);
  36.         ymax = max(ymax, Y[i]);
  37.     }
  38.  
  39.     lli l = xmin, r = xmax;
  40.     lli mnx = INF;
  41.     while(l <= r){
  42.         lli mid = (l + r) / 2;
  43.         lli DisRight = DistanceX(mid + 1);
  44.         lli DisLeft = DistanceX(mid - 1);
  45.         if(DisLeft < DisRight){
  46.             r = mid - 1;
  47.             mnx = min(mnx, DisLeft);
  48.         }
  49.         else{
  50.             l = mid + 1;
  51.             mnx = min(mnx, DisRight);
  52.         }
  53.     }
  54.  
  55.     l = ymin, r = ymax;
  56.     lli mny = INF;
  57.     while(l <= r){
  58.         lli mid = (l + r) / 2;
  59.         lli DisRight = DistanceY(mid + 1);
  60.         lli DisLeft = DistanceY(mid - 1);
  61.         if(DisLeft < DisRight){
  62.             r = mid - 1;
  63.             mny = min(mny, DisLeft);
  64.         }
  65.         else{
  66.             l = mid + 1;
  67.             mny = min(mny, DisRight);
  68.         }
  69.     }
  70.  
  71.     printf("%lld", mnx + mny);
  72.  
  73.     return 0;
  74. }
  75.  
Advertisement
RAW Paste Data Copied
Advertisement