BOJ 2796 - 만남

BOJ 2796 - 만남

처음엔 $x$의 변화와 $y$의 변화를 따로 고려하고 그 중 큰 것이 정답인줄 알았으나 아니다.

정말 직사각형을 계속해서 움직여줘야한다.

직사각형이 선이나 점이 될 수도 있다.

처음에 직사각형의 구간을 $(x_0-p_0 \sim x_0+p_0, y_0-p_0 \sim y_0+p_0)$ 으로 잡자.

이제 $i+1$ 번째 직사각형이 이것과 겹치면 직사각형의 범위를 줄여준다.

만약 겹치지 않으면 $x$와 $y$ 중 더 크게 이동해야 하는것을 $d$ 라고 하자.

그럼 현재 직사각형을 상하좌우로 $d$ 씩 넓혀주고 $i+1$ 번째 직사각형과의 겹치는 부분을 찾으면 그곳이 바로 $d$ 를 이동해서 다시 갈 수 있는 영역이 된다.

직사각형들을 순서대로 움직여줘야 하므로 이 과정을 쭉 진행하면 $O(n)$ 이다.

void solve() {
   int n;
   cin >> n;
   vector<pi> X(n), Y(n);
   for (int i = 0; i < n; i++) {
      int x, y, p;
      cin >> x >> y >> p;
      // [x-p, x+p] ~ [y-p, y+p]
      X[i] = {x - p, x + p};
      Y[i] = {y - p, y + p};
   }
   int ans = 0;
   {
      int xans = 0;
      int xl = X[0].fi, xr = X[0].se, yl = Y[0].fi, yr = Y[0].se;
      for (int i = 1; i < n; i++) {

         if (xl <= X[i].se && xr >= X[i].fi && yl <= Y[i].se && yr >= Y[i].fi) {
            maxa(xl, X[i].fi);
            mina(xr, X[i].se);
            maxa(yl, Y[i].fi);
            mina(yr, Y[i].se);
         } else {
            int dx = xl <= X[i].se && xr >= X[i].fi ? 0 : min(abs(X[i].fi - xr), abs(X[i].se - xl));
            int dy = yl <= Y[i].se && yr >= Y[i].fi ? 0 : min(abs(Y[i].fi - yr), abs(Y[i].se - yl));
            int move = max(abs(dx), abs(dy));
            ans += move;

            assert(dx || dy);

            xl -= move;
            xr += move;
            yl -= move;
            yr += move;

            maxa(xl, X[i].fi);
            mina(xr, X[i].se);
            maxa(yl, Y[i].fi);
            mina(yr, Y[i].se);
         }
      }
      maxa(ans, xans);
      debug(xans);
   }
   cout << ans;
}