When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

LucianIlea's blog

By LucianIlea, 10 years ago, In English

This topic is about CEOI 2012 — "Circuit" task (day 1, task2). In a few words, you are given the coordinates for all vertices of a polygon and you are to determine those vertices visible from (0,0) point. All vertices are situated in the first quadrant. The official solution starts with some good idea: for every point consider its polar angle and determine the point having the less and the greatest such angle. Now we can ignore "the upper part", but this idea will become obsolete, as we will soon see.
The official solution continues with some fuzzy observations (I think there are some mistakes in typewriting) and finally needs some structure in which deletion must happen very fast.
I must recognize the idea seemed to be very clever at the beginning, but... Why not the following solution?
- construct a function turn(a,b,c) which returns 0 if P[a],P[b],P[c] are co-linear, 1 if P[c] is on the left of P[a]P[b], -1 if P[c] is on the right of P[a]P[b]
- after determining the first and the last points (those having the less and the greatest polar angle) use a stack, S, containing points
- at the beginning S.push(first)
- for all other points, i, considered in the order in which they go from first to last, on the "lower" part of the polygon
— if S contains only one element, then S.push(i) — if turn(0,S.top(),i)==1, then S.push(i) — if turn(0,S.top(),i)==-1, then examine the position of i relative to the segment determined by the top two points from S and ignore i or S.pop(), if turn is -1 or 1 This idea is also used by an algorithm for determining the convex hull for a set of planar points and I think it is much more easy to understand and implement.

I hope you will understand my idea and have constructive opinion, instead blindly press dislike button.

  • Vote: I like it
  • +3
  • Vote: I do not like it