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

문제 요약

• 2차원상에 n개의 점과 정수 k가 주어지면, 점 k개를 정확히 제거한 뒤 남은 $n−k$점에 대해 직선 $f(x)=ax+b$를 골라 최대 수직오차 $max |yi−f(xi)|$를 최소화한다. $(n ≤ 50000, k ≤ min(\frac{n}{2}, 300))$
• 구해야 할 값은 “최소 가능한 최대오차” 즉, 제거 후 최적 직선과 점들의 최대 수직 거리이다.

1) 문제를 푸는 관점

• 모든 t=0…k에 대해 위 과정을 수행, 얻은 폭의 최솟값을 고른 뒤, 정답(오차)은 그 절반을 출력한다.

  (위/아래 경계선 사이 전체 폭의 절반이 최대 편차이기 때문)

• 최소 오차 =“어떤 기울기의 직선 주변에 세운 세로 폭을 최소화” ⇒ 두 개의 평행선(위/아래 경계선) 사이에 점들을 최대한 많이 담고, 나머지 k개는 밖으로 밀어낸다.

• 한 기울기(방향)에서 “왼쪽(또는 위쪽)으로 버리는 개수”와 “오른쪽(또는 아래쪽)으로 버리는 개수”의 합이 k가 되면 된다.

  → 결국 한쪽에 정확히 t개가 있게 만드는 방향성 직선들과, 반대쪽에 k-t개가 있게 만드는 맞은편 방향 직선을 짝지어 폭을 계산하면 된다.

2) 전처리 — Convex Layer

• Convex Layer란? 정점들이 주어져 있으면 Convex Hull을 만들고, 그 Convex Hull을 제외한 나머지 점들로 또 Convex Hull을 만들고.. 이를 반복해서 만든 여러개의 Convex Hull을 말한다.

• 입력 점들을 바깥 껍질부터 벗겨가며 Convex Layer를 만든다(최대 $k$개까지만 필요).

  • Convex Layer를 만드는 이유: 회전하며 점을 만날 때 피벗을 바꾸는 동작을 빠르게 하려면, 현재 상태에서 회전했을때 가장 먼저 만나는 점 2개를 알아야 한다.

  

  • 위의 그림의 경우 C(파란색 동그라미 친 원)을 중심으로 반시계방향으로 직선이 회전한다고 하자. 그러면 일단 convex Layer k개보다 안쪽을 볼 필요가 없다. 왜냐하면 k개의 안쪽을 보면 최소 껍질엔 점이 1개씩은 있고, 이게 k개있다는 한쪽면에 점이 k개이상 있다는 것이다. 우리는 k개 이상의 점에 대해서는 신경 쓸 필요가 없다.
  • 볼록다각형의 특성상 이렇게 하면 최대 2k개의 점을 보기만 하면 된다. (빨간색 동그라미 친 점 3개 + 초록색 동그라미 친 점 3개)

3) 회전 스윕 + 피벗 교대로 한쪽에 정확히 t개인 모든 방향 열거

• 기준점에서 시작해, 다른 점을 찍고 직선을 반시계 방향으로 회전한다.

  선이 새 점을 스치면 그 점으로 피벗 교대(회전 축 변경). 이 과정을 반복하면, 선의 한쪽에 있는 점 개수가 이벤트마다 $\pm1$개씩만 바뀐다.

• 이렇게 얻는 경로는 사실상 t-레벨을 걷는 것과 같아서, “한쪽에 정확히 t개” 를 만드는 모든 방향성 직선을 중복 없이 전부 얻게 된다. (t-level: 점–직선 dual에서 각 점 $(a,b)$은 직선 $y=ax−b$, 직선 $y=mx+c$는 점 $(m,c)$로 대응된다. 이때 $(m,c)$의 아래에 정확히 t개의 dual 직선이 놓이는 점들의 자취가 t-level이며, 이는 연속된 사슬을 이룬다.)