l*z
2 楼
凹凸应该是不定的，跟给的点分布有关
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
z*8
3 楼
凸
反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
l*z
4 楼
跟travelling salesman problem差不多。NP-hard problem.
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
b*g
5 楼
.
.
. .
这样的怎么凸？
【在 z********8 的大作中提到】
: 凸
: 反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
.
. .
这样的怎么凸？
【在 z********8 的大作中提到】
: 凸
: 反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
f*h
6 楼
123连起来，一个钝角三角形
题目没有说必须包括所有点
【在 b*****g 的大作中提到】
: .
: .
: . .
: 这样的怎么凸？
题目没有说必须包括所有点
【在 b*****g 的大作中提到】
: .
: .
: . .
: 这样的怎么凸？
l*z
7 楼
再考虑多一点
题目其实出的不严格，因为任意n点并不一定能练成n边行
比如所有点都在一条直线上的情况。
如果题意是所有点都连在一起，那就跟TSP一模一样。
如果题意是允许有些点不相连，但被n-m边行包围在中间，就是个凸边形
【在 l**z 的大作中提到】
: 跟travelling salesman problem差不多。NP-hard problem.
题目其实出的不严格，因为任意n点并不一定能练成n边行
比如所有点都在一条直线上的情况。
如果题意是所有点都连在一起，那就跟TSP一模一样。
如果题意是允许有些点不相连，但被n-m边行包围在中间，就是个凸边形
【在 l**z 的大作中提到】
: 跟travelling salesman problem差不多。NP-hard problem.
b*g
8 楼
n个点 n边形
【在 f*****h 的大作中提到】
: 123连起来，一个钝角三角形
: 题目没有说必须包括所有点
【在 f*****h 的大作中提到】
: 123连起来，一个钝角三角形
: 题目没有说必须包括所有点
w*t
9 楼
nod这个题目不严谨
【在 b*****g 的大作中提到】
: n个点 n边形
【在 b*****g 的大作中提到】
: n个点 n边形
相关阅读