Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define pb emplace_back
- using namespace std;
- using ll = long long;
- const int maxn = 100010;
- int n, x[maxn], y[maxn], w[maxn];
- const ll inf = 1ll << 59;
- ll res;
- int res_x, res_y;
- ll get_cost(int X, int Y){
- ll res = 0;
- for(int i = 0;i < n;++i)res += (ll)min(abs(x[i]-X), abs(Y-y[i])) * w[i];
- return res;
- }
- void jump(int cx, int cy){
- int step_size = 1<<29;
- while(step_size > 0){
- bool isbest = false;
- while(!isbest){
- isbest = true;
- for(int dx : {-step_size, 0, step_size})for(int dy : {-step_size, 0, step_size})if(dx || dy){
- if(ll tmp = get_cost(dx+cx, dy+cy); tmp < res || (tmp == res && (dx < 0 || (dx == 0 && dy < 0)))){
- res = tmp;
- cx += dx, cy += dy;
- res_x = cx, res_y = cy;
- isbest = false;
- }
- }
- }
- step_size /= 2;
- }
- }
- void solve(){
- cin >> n;
- for(int i = 0;i < n;++i)cin >> x[i] >> y[i], w[i] = 1;
- res = inf;
- tie(res_x, res_y) = pair<int,int>{0,0};
- //res_x = 104, res_y = 1399;
- res = get_cost(res_x, res_y);
- jump(res_x, res_y);
- cout << res_x << ' ' << res_y << '\n';
- }
- signed main(){
- ios_base::sync_with_stdio(0), cin.tie(0);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement