给定平面上 nnn 个点的坐标和 mmm 条边,边之间不相交,若一个多边形(可以是凹多边形)内部没有多边形,就称它为最小多边形。输出求出图中所有的最小多边形。
例如说对于下面的图,最小多边形有 [1,2,3][1, 2, 3][1,2,3] [2,3,5,4][2, 3, 5, 4][2,3,5,4] [1,2,4,6][1, 2, 4, 6][1,2,4,6]。而 [1,3,2,4,6][1, 3, 2, 4, 6][1,3,2,4,6] 内部有多边形,不是最小多边形。
大佬有没有 O(n2)O(n^2)O(n2) 或者更优秀的做法?(假设 nnn 和 mmm 同阶),万分感谢!
(口胡的,不保证有比较简单的方法)