search

Luzhiled / comp-geometry

C++ geometry library for ICPC
https://luzhiled.github.io/comp-geometry/
6 stars 3 forks source link

点の多角形内部判定と点の凸多角形内部判定を分ける #5

Open Luzhiled opened 4 years ago

Luzhiled commented 4 years ago

後者は O(log n) でできる

関数名の suffix に _polygon とか _convex とかつけてわける？

Luzhiled commented 4 years ago

#113 B Polygons

Luzhiled commented 4 years ago

ccw の二分探索 + 点の三角形内包判定だけで解けるはず

二分探索パートで得られる辺は応用が効くので contain_convex とは別の関数にする

Luzhiled commented 3 years ago

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0412?year=2019