search

VictorXjoeY / Notebook

Notebook used for competitive programming!
11 stars 2 forks source link

Fix Winding Number Algorithm #20

Closed VictorXjoeY closed 4 years ago

VictorXjoeY commented 4 years ago

Geometry/point_inside_polygon.cpp

It fails on https://open.kattis.com/problems/pointinpolygon

VictorXjoeY commented 4 years ago

Code is updated to match consider these rules: http://geomalgorithms.com/a03-_inclusion.html#Edge-Crossing-Rules

And to match with this implementation: http://geomalgorithms.com/a03-_inclusion.html#wn_PnPoly()

But it still gives WA on: https://open.kattis.com/problems/pointinpolygon

VictorXjoeY commented 4 years ago

Fixed. The problem was actually in point_inside_segment(q, a, b) which was not properly treating the degenerate case when a == b.