Невозможно отладить код для 686E на Codeforces

Question

Я искал проблему this, но не увенчался успехом.

Проблема: «Учитывая набор исходных точек в плоскости, найдите точку (с целыми координатами), так что максимальное расстояние Манхэттена до любой из исходных точек минимизируется».

Я нашел very similar problem в Google Code Jam, который я успешно разрешил с помощью своего Анализа Конкурса.

Мой подход очень похож на решение проблемы с замятием кода, адаптированное к целочисленному ограничению в проблеме CodeForces.

Насколько я могу судить по деталям неправильных тестовых случаев, мой ответ «недостаточно хорош», т. Е. Существует точка с меньшим максимальным расстоянием.

К сожалению, я не могу связать свой код (ограничение по двум ссылкам), поэтому я скопировал его ниже.

#include <iostream> 
#include <iomanip> 
#include <cmath> 

#define setMax(a, b) (a<b)?(a=b):0 
#define setMin(a, b) (a>b)?(a=b):0 

using namespace std; 

const int N = (int)1e5; 
const long long LL_UP = (long long)9e18; 

struct point 
{ 
    long long x, y, z; 

}s[N]; 

bool doesAnswerExist(long long c, int n, point &ans) 
{ 
    long long A, B, C, D, E, F, G, H; 
    A = C = E = G = -LL_UP; 
    B = D = F = H = LL_UP; 

    for (int i = 0; i < n; ++i) 
    { 
     setMax(A, s[i].x + s[i].y + s[i].z - c); 
     setMin(B, s[i].x + s[i].y + s[i].z + c); 
     setMax(C, -s[i].x + s[i].y + s[i].z - c); 
     setMin(D, -s[i].x + s[i].y + s[i].z + c); 
     setMax(E, s[i].x - s[i].y + s[i].z - c); 
     setMin(F, s[i].x - s[i].y + s[i].z + c); 
     setMax(G, s[i].x + s[i].y - s[i].z - c); 
     setMin(H, s[i].x + s[i].y - s[i].z + c); 
    } 

    if (A > B or C > D or E > F or G > H) 
     return false; 

    long long xMin = ceil(max((G+E)/2.0, (A-D)/2.0)), xMax = floor(min((B-C)/2.0, (H+F)/2.0)); 

    if (xMin > xMax) 
     return false; 

    for (ans.x = xMin; ans.x <= xMax; ++ans.x) 
    { 
     long long ypz = max(A-ans.x, C+ans.x), ymz = max(ans.x-F, G-ans.x); 

     if ((long long)fabs(ymz + ypz) % 2 == 1) 
     { 
      if (ypz < min(B-ans.x, D+ans.x)) 
       ++ypz; 

      else if (ymz < min(ans.x-E, H-ans.x)) 
       ++ymz; 

      else 
       continue; 
     } 

     ans.y = (ypz+ymz)/2; 
     ans.z = (ypz-ymz)/2; 
     return true; 
    } 

    return false; 
} 

void binSearch(long long l, long long r, int n, point &ans) 
{ 
    if (l == r) 
    { 
     doesAnswerExist(l, n, ans); 
     return; 
    } 

    long long mid = (l+r)/2; 

    if (doesAnswerExist(mid, n, ans)) 
     binSearch(l, mid, n, ans); 

    else 
     binSearch(mid+1, r, n, ans); 
} 

int main() 
{ 
    ios_base::sync_with_stdio(false); 

    int t, n; 

    cin >> t; 

    while (t--) 
    { 
     cin >> n; 

     for (int i = 0; i < n; ++i) 
      cin >> s[i].x >> s[i].y >> s[i].z; 

     point ans; 
     binSearch(0, (long long)3e18, n, ans); 

     cout << ans.x << ' ' << ans.y << ' ' << ans.z << '\n'; 
    } 

    return 0; 
} 

Answer 1

Я решил это сам, надо сказать, это была самая глупая ошибка, которую я когда-либо делал.

Я глупо полагал, что деление целого на 2 даст мне пол (x/2), но, как я только что выяснил, это неверно для отрицательных чисел, так как int (-2.5) даст -2 а не -3.