求助一个简单的图论问题,玄关
  • 板块学术版
  • 楼主sms123
  • 当前回复20
  • 已保存回复21
  • 发布时间2025/7/29 14:33
  • 上次更新2025/7/29 19:16:34
查看原帖
求助一个简单的图论问题,玄关
596783
sms123楼主2025/7/29 14:33

给定平面上 nn 个点的坐标和 mm 条边,边之间不相交,若一个多边形(可以是凹多边形)内部没有多边形,就称它为最小多边形。输出求出图中所有的最小多边形。

例如说对于下面的图,最小多边形有 [1,2,3][1, 2, 3] [2,3,5,4][2, 3, 5, 4] [1,2,4,6][1, 2, 4, 6]。而 [1,3,2,4,6][1, 3, 2, 4, 6] 内部有多边形,不是最小多边形。

大佬有没有 O(n2)O(n^2) 或者更优秀的做法?(假设 nnmm 同阶),万分感谢!

(口胡的,不保证有比较简单的方法)

2025/7/29 14:33
加载中...