【华为练习题】求最大凸多边形（高级）

本文主要是介绍【华为练习题】求最大凸多边形（高级），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【华为练习题】求最大凸多边形（高级）

题目

题目描述：
给定一些点，输出最大面积的凸边形。输出起始点为x轴最左边的点，按照顺时针方向输出，每个点必须是凸边形的顶点（不输出边上或凸边形内的点）。输入第一个数n为坐标点个数，后面依次为n个坐标点的坐标，横坐标在前，不同坐标点用‘；’隔开，相同坐标点的横纵坐标用‘，’隔开。
输入样例：
13;-4,1;-2,3;1,3;2,2;1,4;5,4;6,1;2,-4;-3,-3;1,-1;-2,-2;1,-2;-1,-1
输出样例：
-4,1;-2,3;1,4;5,4;6,1;2,-4;-3,-3
注：
- 输入数据的第一个数为点的数目，然后是分号；再后面就是以分号间隔的点；
- 点的数目最少为3个，最多为65535；
- 该题目和斜率相关。

分析

从横坐标最小的点，斜率为正无限开始，依次寻找下一个坐标点。具体过程为，求出该点与其它所有点的斜率，找到小于当前斜率的前提下能形成最大斜率且横坐标大于等于该点的点。直到找到横坐标最大的点为止。再从该点，斜率为正无限开始，依次寻找下一个坐标点。具体过程为，求出该点与其它所有点的斜率，找到小于当前斜率的前提下能形成最大斜率且横坐标小于等于该点的点。直到找到初始位置为止。

解答

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;struct Point
{Point(int a, int b):x(a),y(b) {};int x,y;
};// 判断字符是否为分隔符
inline bool