DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Tour

Back to problem

Editorial

Compute the convex hull of all points and let its area be AAA.

If the convex hull is a segment, sort the points lexicographically by (Xi,Yi)(X_i,Y_i)(Xi​,Yi​) and output that order. Now suppose the convex hull has positive area.

Set the strip spacing to h=2ANh=\sqrt{\frac{2A}{N}}h=N2A​​ and let . Use the following two horizontal grids: and , where is an integer.

For each grid, build one candidate tour as follows.

  1. Assign every point to its nearest grid line.
  2. Process the grid lines from bottom to top. If the grid-line index kkk is even, visit the assigned points in increasing order of XXX; if it is odd, visit them in decreasing order of XXX.
  3. Connect the last point back to the first point.

Compute the lengths of the two candidate tours and output the shorter one. The convex hull and its area can be computed in O(Nlog⁡N)O(N\log N)O(NlogN) time, so the whole algorithm runs in O(Nlog⁡N)O(N\log N)O(NlogN) time.

Proof

Let WWW, PPP, and DDD be the horizontal width, perimeter, and diameter of the convex hull. We have W≤DW\le DW≤D.

Fix one grid. Project every point vertically onto its assigned horizontal line. Expand the convex hull upward and downward by h2\frac{h}{2}. Every projected point lies inside the expanded convex body. Its area is , its perimeter is , and its diameter is at most .

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

Imagine traversing every horizontal segment obtained by intersecting the expanded body with a grid line. Move from bottom to top, traversing one segment from left to right and the next from right to left. Connect the endpoints of consecutive segments on the same side by a straight segment. Such a segment is no longer than the corresponding boundary arc of the convex body. Therefore, the total cost of connecting consecutive horizontal segments is at most P+2hP+2hP+2h, and closing the walk costs at most D+hD+hD+h.

Whenever the walk reaches a projected point, make a round trip to the original point. After all points have been visited, shortcut auxiliary points using the triangle inequality. The tour produced by the algorithm is no longer than this auxiliary walk.

The two grids are shifted by h2\frac{h}{2}2h​. For every point, the sum of its distances to the nearest line of the first grid and the nearest line of the second grid is h2\frac{h}{2}2h​. Hence the average round-trip cost from the grid lines to the original points is Nh2\frac{Nh}{2}2Nh​ over the two candidates.

Let f(y)f(y)f(y) be the horizontal cross-section length of the expanded convex body at height yyy. The union of the two grids is a grid with spacing h2\frac{h}{2}2h​. By convexity, f(y)f(y)f(y) first increases and then decreases, so its total variation is at most 2W2W2W. Bounding the difference between the Riemann sum on this grid and the integral by the total variation shows that the average horizontal movement of the two candidates is at most Ah+2W\frac{A}{h}+2WhA​+2W.

Therefore, one of the two candidates has length LLL satisfying

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.

Since h=2ANh=\sqrt{\frac{2A}{N}}h=N2A​​, the first two terms sum to 2AN\sqrt{2AN}2AN​. For a planar convex body of diameter DDD, we have A≤πD24A\le\frac{\pi D^2}{4}A≤4πD2​, W≤DW\le DW≤D, and P≤πDP\le\pi DP≤πD. Also, N≥3N\ge3N≥3 gives 3h≤3Dπ63h\le3D\sqrt{\frac{\pi}{6}}3h≤3D6π​. Thus

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).

If the convex hull is a segment, the lexicographic order gives a tour of length at most 2D2D2D, so the same bound holds.

​
<