Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ll l1 = -INF, r1 = INF, l2 = -INF, r2 = INF;
- struct Pt {
- int x, y;
- } a[N];
- bool cmp(Pt a, Pt b) {
- return a.y < b.y;
- }
- ld calc2(ld x, ld y, int n) {
- ld ans = 0;
- for (int i = 0; i < n; i++)
- ans += abs(a[i].x - x) + abs(a[i].y - y);
- return ans;
- }
- pair <ld, ld> calc(ld x, int n) { /// (dist, y)
- ld ly = max(x - r2, l1 - x), ry = min(r1 - x, x - l2);
- if (ly > ry)
- return {INF, INF};
- ld val = calc2(x, ly, n);
- ll ansy = ly;
- ld midy1 = a[n / 2].y;
- ld temp = calc2(x, ry, n);
- if (temp < val)
- val = temp, ansy = ry;
- if (midy1 >= ly && midy1 <= ry) {
- temp = calc2(x, midy1, n);
- if (val > temp)
- val = temp, ansy = midy1;
- }
- if (n % 2 == 0) {
- midy1 = a[(n - 1) / 2].y;
- if (midy1 >= ly && midy1 <= ry) {
- temp = calc2(x, midy1, n);
- if (val > temp)
- val = temp, ansy = midy1;
- }
- }
- return {val, ly};
- }
- int main() {
- init();
- //ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- //cin >> a[i].x >> a[i].y;
- scanf("%d %d", &a[i].x, &a[i].y);
- }
- sort(a, a + n, cmp);
- ll d;
- cin >> d;
- for (int i = 0; i < n; i++) {
- l1 = max(l1, (ll)a[i].x + a[i].y - d);
- r1 = min(r1, (ll)a[i].x + a[i].y + d);
- l2 = max(l2, (ll)a[i].x - a[i].y - d);
- r2 = min(r2, (ll)a[i].x - a[i].y + d);
- }
- //cout << l1 << " " << r1 << endl;
- ld lx = (l1 + l2) / 2., rx = (r1 + r2) / 2.;
- for (int i1 = 0; i1 < M; i1++) {
- ld m1 = (lx + lx + rx) / 3;
- ld m2 = (lx + rx + rx) / 3;
- //cout << m1 << ' ' << m2 << endl;
- auto c1 = calc(m1, n);
- auto c2 = calc(m2, n);
- if (c1.first > c2.first)
- lx = m1;
- else
- rx = m2;
- }
- ll z = lx;
- ll ans = calc(z, n).first;
- ans = min(ans, (ll)calc(z + 1, n).first);
- if (ans >= INF)
- cout << "impossible";
- else
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement