Advertisement
Guest User

Untitled

a guest
Oct 19th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.06 KB | None | 0 0
  1.  
  2. ll l1 = -INF, r1 = INF, l2 = -INF, r2 = INF;
  3.  
  4. struct Pt {
  5. int x, y;
  6. } a[N];
  7.  
  8. bool cmp(Pt a, Pt b) {
  9. return a.y < b.y;
  10. }
  11.  
  12. ld calc2(ld x, ld y, int n) {
  13. ld ans = 0;
  14. for (int i = 0; i < n; i++)
  15. ans += abs(a[i].x - x) + abs(a[i].y - y);
  16. return ans;
  17. }
  18.  
  19. pair <ld, ld> calc(ld x, int n) { /// (dist, y)
  20. ld ly = max(x - r2, l1 - x), ry = min(r1 - x, x - l2);
  21. if (ly > ry)
  22. return {INF, INF};
  23. ld val = calc2(x, ly, n);
  24. ll ansy = ly;
  25. ld midy1 = a[n / 2].y;
  26. ld temp = calc2(x, ry, n);
  27. if (temp < val)
  28. val = temp, ansy = ry;
  29. if (midy1 >= ly && midy1 <= ry) {
  30. temp = calc2(x, midy1, n);
  31. if (val > temp)
  32. val = temp, ansy = midy1;
  33. }
  34. if (n % 2 == 0) {
  35. midy1 = a[(n - 1) / 2].y;
  36. if (midy1 >= ly && midy1 <= ry) {
  37. temp = calc2(x, midy1, n);
  38. if (val > temp)
  39. val = temp, ansy = midy1;
  40. }
  41. }
  42. return {val, ly};
  43. }
  44.  
  45. int main() {
  46. init();
  47. //ios_base::sync_with_stdio(false);
  48. int n;
  49. cin >> n;
  50. for (int i = 0; i < n; i++) {
  51. //cin >> a[i].x >> a[i].y;
  52. scanf("%d %d", &a[i].x, &a[i].y);
  53. }
  54. sort(a, a + n, cmp);
  55. ll d;
  56. cin >> d;
  57.  
  58. for (int i = 0; i < n; i++) {
  59. l1 = max(l1, (ll)a[i].x + a[i].y - d);
  60. r1 = min(r1, (ll)a[i].x + a[i].y + d);
  61. l2 = max(l2, (ll)a[i].x - a[i].y - d);
  62. r2 = min(r2, (ll)a[i].x - a[i].y + d);
  63. }
  64.  
  65. //cout << l1 << " " << r1 << endl;
  66.  
  67. ld lx = (l1 + l2) / 2., rx = (r1 + r2) / 2.;
  68. for (int i1 = 0; i1 < M; i1++) {
  69. ld m1 = (lx + lx + rx) / 3;
  70. ld m2 = (lx + rx + rx) / 3;
  71. //cout << m1 << ' ' << m2 << endl;
  72. auto c1 = calc(m1, n);
  73. auto c2 = calc(m2, n);
  74. if (c1.first > c2.first)
  75. lx = m1;
  76. else
  77. rx = m2;
  78. }
  79.  
  80. ll z = lx;
  81. ll ans = calc(z, n).first;
  82. ans = min(ans, (ll)calc(z + 1, n).first);
  83. if (ans >= INF)
  84. cout << "impossible";
  85. else
  86. cout << ans;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement