| 5 | return abs(real(a) - real(b)) > EPS ? |
| 6 | real(a) < real(b) : imag(a) < imag(b); } |
| 7 | int convex_hull(polygon p) { |
| 8 | int n = size(p), l = 0; |
| 9 | sort(p.begin(), p.end(), cmp); |
| 10 | rep(i,0,n) { |
| 11 | if (i > 0 && p[i] == p[i - 1]) continue; |
| 12 | while (l >= 2 && |
| 13 | ccw(hull[l - 2], hull[l - 1], p[i]) >= 0) l--; |
| 14 | hull[l++] = p[i]; } |
| 15 | int r = l; |
| 16 | for (int i = n - 2; i >= 0; i--) { |
| 17 | if (p[i] == p[i + 1]) continue; |
| 18 | while (r - l >= 1 && |
| 19 | ccw(hull[r - 2], hull[r - 1], p[i]) >= 0) r--; |
| 20 | hull[r++] = p[i]; } |
| 21 | return l == 1 ? 1 : r - 1; } |
| 22 | // vim: cc=60 ts=2 sts=2 sw=2: |