| 9 | #define CHK(f,a,b,c) \ |
| 10 | (f(a) < f(b) && f(b) <= f(c) && ccw(a,c,b) < 0) |
| 11 | int point_in_polygon(polygon p, point q) { |
| 12 | int n = size(p); bool in = false; double d; |
| 13 | for (int i = 0, j = n - 1; i < n; j = i++) |
| 14 | if (collinear(p[i], q, p[j]) && |
| 15 | 0 <= (d = progress(q, p[i], p[j])) && d <= 1) |
| 16 | return 0; |
| 17 | for (int i = 0, j = n - 1; i < n; j = i++) |
| 18 | if (CHK(real, p[i], q, p[j]) || CHK(real, p[j], q, p[i])) |
| 19 | in = !in; |
| 20 | return in ? -1 : 1; } |
| 21 | pair<polygon, polygon> cut_polygon(const polygon &poly, |
| 22 | point a, point b) { |
| 23 | polygon left, right; point it; |