DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Tour

返回题目

题解

모든 점의 볼록 껍질을 구하고, 그 넓이를 AAA라고 하자.

볼록 껍질이 선분이면 점들을 (Xi,Yi)(X_i,Y_i)(Xi​,Yi​)의 사전순으로 정렬하여 출력한다. 이제 볼록 껍질의 넓이가 양수인 경우를 생각하자.

띠의 간격을 h=2ANh=\sqrt{\frac{2A}{N}}h=N2A​​으로 정하고, 라고 하자. 다음 두 수평선 격자를 사용한다: 와 . 여기서 는 정수이다.

각 격자에 대해 다음과 같이 후보 순회를 만든다.

  1. 각 점을 가장 가까운 격자선에 배정한다.
  2. 격자선을 아래에서 위로 보면서, 격자선 번호 kkk가 짝수이면 배정된 점들을 XXX 오름차순으로, 홀수이면 XXX 내림차순으로 방문한다.
  3. 마지막 점과 첫 점을 연결한다.

두 후보의 순회 길이를 계산하고 더 짧은 후보를 출력한다. 볼록 껍질과 넓이는 O(Nlog⁡N)O(N\log N)O(NlogN)에 구할 수 있으므로 전체 시간복잡도는 O(Nlog⁡N)O(N\log N)O(NlogN)이다.

증명

볼록 껍질의 가로 폭을 WWW, 둘레를 PPP, 지름을 DDD라고 하자. W≤DW\le DW≤D이다.

하나의 격자를 고정하자. 각 점을 자신이 배정된 수평선으로 수직 투영한다. 볼록 껍질을 위아래로 h2\frac{h}{2}만큼 확장한 볼록도형을 생각하면 모든 투영점이 이 도형 안에 들어간다. 확장된 도형의 넓이는 , 둘레는 , 지름은 이하이다.

Solution written by GPT5.6

Ymin⁡=min⁡iYiY_{\min}=\min_iY_iYmin​=mini​Yi​
Y=Ymin⁡+khY=Y_{\min}+khY=Ymin​+kh
Y=Ymin⁡+(k+12)hY=Y_{\min}+(k+\frac12)hY=Ymin​+(k+21​)h
kkk
2h​
A+hWA+hWA+hW
P+2hP+2hP+2h
D+hD+hD+h

각 격자선과 확장된 도형의 교집합인 수평 선분 전체를 방문한다고 생각하자. 아래에서 위로 올라가며 한 선분은 왼쪽에서 오른쪽으로, 다음 선분은 오른쪽에서 왼쪽으로 지난다. 연속한 두 선분의 끝점을 같은 쪽에서 직선으로 연결하면 그 길이는 두 끝점을 잇는 볼록도형의 경계 호보다 길지 않다. 따라서 선분 사이를 연결하는 길이의 합은 P+2hP+2hP+2h 이하이고, 마지막 위치에서 처음 위치로 돌아가는 길이는 D+hD+hD+h 이하이다.

투영점에 도착할 때마다 원래 점까지 갔다가 돌아오는 보조 순회를 생각한다. 보조점을 삼각부등식으로 제거하면 알고리즘이 만든 순회의 길이는 이 보조 순회보다 길지 않다.

두 격자는 h2\frac{h}{2}2h​만큼 어긋나 있다. 임의의 점에서 첫 번째 격자의 가장 가까운 선까지의 거리와 두 번째 격자의 가장 가까운 선까지의 거리의 합은 h2\frac{h}{2}2h​이다. 따라서 두 후보에서 원래 점까지 왕복하는 비용의 평균은 Nh2\frac{Nh}{2}2Nh​이다.

높이 yyy에서 확장된 볼록도형의 수평 단면 길이를 f(y)f(y)f(y)라고 하자. 두 격자를 합치면 간격이 h2\frac{h}{2}2h​인 하나의 격자가 된다. 볼록성 때문에 f(y)f(y)f(y)는 증가한 뒤 감소하며 전체 변동량은 2W2W2W 이하이다. 이 격자의 리만 합과 적분의 차이를 전체 변동량으로 상계하면 두 후보의 수평 이동량의 평균은 Ah+2W\frac{A}{h}+2WhA​+2W 이하이다.

따라서 두 후보 중 하나의 길이 LLL은 다음을 만족한다.

L≤Ah+Nh2+2W+P+D+3h.L\le \frac{A}{h}+\frac{Nh}{2}+2W+P+D+3h.L≤hA​+2Nh​+2W+P+D+3h.

h=2ANh=\sqrt{\frac{2A}{N}}h=N2A​​이므로 처음 두 항의 합은 2AN\sqrt{2AN}2AN​이다. 지름이 DDD인 평면 볼록도형에 대해 A≤πD24A\le\frac{\pi D^2}{4}A≤4πD2​, W≤DW\le DW≤D, P≤πDP\le\pi DP≤πD가 성립한다. 또한 N≥3N\ge3N≥3이므로 3h≤3Dπ63h\le3D\sqrt{\frac{\pi}{6}}3h≤3D6π​이다. 따라서

L≤DπN2+(π+3+3π6)D<D(πN2+10).L\le D\sqrt{\frac{\pi N}{2}}+\left(\pi+3+3\sqrt{\frac{\pi}{6}}\right)D<D\left(\sqrt{\frac{\pi N}{2}}+10\right).L≤D2πN​​+(π+3+36π​​)DD(2πN​​+10).

볼록 껍질이 선분인 경우에는 위 정렬로 얻는 순회의 길이가 2D2D2D 이하이므로 같은 상계를 만족한다.

​
<