search

Ra1nWarden / Online-Judges

My solutions to various online judge problems.
0 stars 0 forks source link

1331 WA #42

Open Ra1nWarden opened 9 years ago

Ra1nWarden commented 9 years ago

DP part is done but need special condition for triangles that cannot be formed by joining points in the polygon. The polygon may be concave so need some computational geometry here.

Ra1nWarden commented 9 years ago

Proposal: Find intersection point between the diagonal and any side of the polygon. These points divide the line into segments. For each segment, find the middle point and determine whether it is inside the polygon.