2796번: SETNJA

https://www.acmicpc.net/problem/2796


$O(n)$

걸음 수가 최소가 되는 구역인
왼쪽 아래 좌표가 (sx,sy), 오른쪽 위 좌표가 (ex,ey)인 직사각형(이하 R)을 생각해보자.(이 직사각형은 변의 길이가 0이 될 수도 있다.)
따라서 R은 처음 만난 친구의 이동범위와 같고 최소 걸음 수는 0이다.
문제에 주어진 걷는 방식의 특성에 따라 그리디적으로 R을 변형시켜 최종 답을 도출해낼 수 있다.

R은 이후 방문한 친구의 이동가능한 구역을 표현한 정사각형(이하 S)과의 위치관계에 따라 변할 것이다.
i) R과 S 사이 겹치는 곳이 있다.
R은 R과 S의 겹치는 부분이 되며 최소 걸음 수는 변하지 않는다.
ii) R과 S 사이 겹치는 곳이 없다.
R을 네 대각선 방향으로 S와 닿을 때까지 균일하게 늘려준다. 이후 R은 S와 닿은 부분인 점 혹은 선분 모양의 구역이 된다. 최소 걸음 수는 처음 R을 늘린만큼 증가한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, sx, sy, ex, ey, x, y, p, t;
long long r;
int main() {
    scanf("%d%d%d%d", &n, &x, &y, &p);
    sx = x - p; sy = y - p;
    ex = x + p; ey = y + p;
    while (--n) {
        scanf("%d%d%d", &x, &y, &p);
        t = max({ x - p - ex,y - p - ey,sx - x - p,sy - y - p,0 });
        sx = max(sx - t, x - p);
        sy = max(sy - t, y - p);
        ex = min(ex + t, x + p);
        ey = min(ey + t, y + p);
        r += t;
    }
    printf("%lld", r);
    return 0;
}