(points []point)
| 19 | } |
| 20 | |
| 21 | func grahamScan(points []point) []point { |
| 22 | sort.Slice(points, func(a, b int) bool { |
| 23 | return points[a].y < points[b].y || (points[a].y == points[b].y && points[a].x < points[b].x) |
| 24 | }) |
| 25 | |
| 26 | start := points[0] |
| 27 | points = points[1:] |
| 28 | |
| 29 | sort.Slice(points, func(a, b int) bool { |
| 30 | return polarAngle(start, points[a]) < polarAngle(start, points[b]) |
| 31 | }) |
| 32 | |
| 33 | hull := []point{start, points[0], points[1]} |
| 34 | for _, p := range points[2:] { |
| 35 | for !counterClockwise(hull[len(hull)-2], hull[len(hull)-1], p) { |
| 36 | hull = hull[:len(hull)-1] |
| 37 | } |
| 38 | hull = append(hull, p) |
| 39 | } |
| 40 | |
| 41 | return hull |
| 42 | } |
| 43 | |
| 44 | func main() { |
| 45 | points := []point{{-5, 2}, {5, 7}, {-6, -12}, {-14, -14}, {9, 9}, |
no test coverage detected