Advertisement
Kevin_Zhang

Untitled

Oct 9th, 2021
1,095
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. using namespace std;
  4. using ll = long long;
  5. const int maxn = 100010;
  6. int n, x[maxn], y[maxn], w[maxn];
  7. const ll inf = 1ll << 59;
  8. ll res;
  9. int res_x, res_y;
  10. ll get_cost(int X, int Y){
  11.     ll res = 0;
  12.     for(int i = 0;i < n;++i)res += (ll)min(abs(x[i]-X), abs(Y-y[i])) * w[i];
  13.     return res;
  14. }
  15. void jump(int cx, int cy){
  16.     int step_size = 1<<29;
  17.     while(step_size > 0){
  18.         bool isbest = false;
  19.         while(!isbest){
  20.             isbest = true;
  21.             for(int dx : {-step_size, 0, step_size})for(int dy : {-step_size, 0, step_size})if(dx || dy){
  22.                 if(ll tmp = get_cost(dx+cx, dy+cy); tmp < res || (tmp == res && (dx < 0 || (dx == 0 && dy < 0)))){
  23.                     res = tmp;
  24.                     cx += dx, cy += dy;
  25.                     res_x = cx, res_y = cy;
  26.                     isbest = false;
  27.                 }
  28.             }
  29.         }
  30.         step_size /= 2;
  31.     }
  32. }
  33. void solve(){
  34.     cin >> n;
  35.     for(int i = 0;i < n;++i)cin >> x[i] >> y[i], w[i] = 1;
  36.     res = inf;
  37.     tie(res_x, res_y) = pair<int,int>{0,0};
  38.     //res_x = 104, res_y = 1399;
  39.     res = get_cost(res_x, res_y);
  40.     jump(res_x, res_y);
  41.     cout << res_x << ' ' << res_y << '\n';
  42. }
  43. signed main(){
  44.     ios_base::sync_with_stdio(0), cin.tie(0);
  45.     solve();
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement