首页 > 试题广场 >

凸多边形

[编程题]凸多边形
  • 热度指数:12 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 50M,其他语言100M
  • 算法知识视频讲解
给出N个平面坐标点(x, y),以这些点为顶点能够组成凸多边形,求其中面积最大的凸多边形的所有边的平方和。N<=10000,0<=x,y<=1000

输入描述:
每组两个整数,分别代表着横坐标和纵坐标,用空格分割。组与组直接用逗号分割。
注意:
1. 可能输入重复的点。
2. 当多个点在同一条边上时,只取两端的点。
3. 当所有的点不能构成多边形时(只能形成一条直线或者一个点),输出0。


输出描述:
输出一个整数。
示例1

输入

0 0,1 0,1 1,2 0,1 1

输出

8

说明

组成多边形的顶点有:(0, 0) (2, 0) (1, 1),边长的平方和为4+2+2=8

起始点开始按逆时针方向依次找到离目前点最近的点就可以了

发表于 2019-08-20 08:17:34 回复(1)