search

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker
https://judge.yosupo.jp/
Apache License 2.0
521 stars 118 forks source link

[Problem suggestion] Convex Layers #582

Closed dragonslayerintraining closed 4 years ago

dragonslayerintraining commented 4 years ago

This problem (nested convex hulls) was discussed here. I forked this repository and was about to create a pull request when I realized I should make an issue first.

yosupo06 commented 4 years ago

Cool! So, could you give me the problem statement first? Rough sketch is enough. We want to adjust the small details for keeping consistency with other problems.

dragonslayerintraining commented 4 years ago

You are given n distinct points in the plane with integer coordinates. While there are points remaining, remove all points on the boundary of the convex hull of the remaining points. For each point, output which iteration it was removed in.

1 <= n <= 200000 0 <= x_i, y_i <= 10^6 Time limit: 5 seconds

My implementation is O(n(logn)^2). The discussion linked above mentions a faster O(nlogn) solution that doesn't seem more complicated, but I haven't looked into it.

yosupo06 commented 4 years ago

Thanks! That sounds good. So, there is no problem to make PR (and I would happy if you help our project). If you have some trouble while preparing the problem, don't hesitate me to ask :)

dragonslayerintraining commented 4 years ago

Some checks were not successful but I don't know why.

dragonslayerintraining commented 4 years ago

Ok, checks passed now.

yosupo06 commented 4 years ago

Thanks for your great and polite job! I reviewed but no problem, so this PR was merged and your problem was appeared in https://judge.yosupo.jp/problem/convex_layers .

(and FYI, I added a japanese statement in #585 )