华为机试题--求最大凸多边形

/** 
求最大凸多边形
给定一些点，输出最大面积的凸边形。输出起始点为x轴最左边的点，按照顺时针方向输出，每个点必须是凸边形的顶点（不输出边上或凸边形内的点）。
输入样例： 
13;-3,-3;1,3;2,-4;6,1;-2,-2;4,5;1,-2;1,4;-2,3;-4,1;-1,1;2,2;1,-1 
输出样例： 
-4,1;-2,3;4,5;6,1;2,-4;-3,-3
注： 
输入数据的第一个数为点的数目，然后是分号；再后面就是以分号间隔的点； 
点的数目最少为3个，最多为65535,点坐标范围[-1000, 1000]；

假设输入的点可以组成一个凸多边形。

这道题是一道凸包问题，假设输入可以组成一个凸多边形，程序中没有加以验证。

我的思路是取左端最左下方的点作为边界点1（left），右端的在最右上方的点作为边界点2（right），分上半部分和下半部分来查找的。

（1）先是以left为起点，顺时针扫描到点left右上部分的第一个点p1，然后以p1为起点，顺时针扫描到点p1右上部分的第一个点p2，重复操作，直到找到点right；

（2）同样原理，以right为起点，顺时针扫描到点right左下部分的第一个点p1‘，然后以p1’为起点，顺时针扫描到点p1‘左下部分的第一个点p2’，重复操作，直到找到点left；

通过以上操作便可以依次得到顺时针到组成最大凸多边形的每一个顶点，如下图所示：

  */ 

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct Point
{
	int x;
	int y;

	explicit Point(int px=0, int py=0):x(px),y(py){}

	bool operator==(const Point& p)
	{
		return (p.x == x) && (p.y == y);
	}

	bool operator!=(const Point& p)
	{
		return !(*this == p);
	}

	bool operator<(const Point& p)
	{
		if(x != p.x)
			return (x < p.x);
		else
			return (y < p.y);
	}

	bool operator>(const Point& p)
	{
		if(x != p.x)
			return (x > p.x);
		else
			return (y > p.y);
	}

};

// 判断点P2是否位于点P1左下侧，用于下半部分查找
inline bool isLeftLowPoint(const Point& p1, const Point& p2)
{
	if(p1.x != p2.x)
		return p1.x > p2.x;
	else
		return p1.y > p2.y;
}

// 判断点P2是否位于点P1右上侧，用于上半部分查找
inline bool isRightUpPoint(const Point& p1, const Point& p2)
{
	if(p1.x != p2.x)
		return p1.x < p2.x;
	else
		return p1.y < p2.y;
}

// 计算斜率K值
inline double calculateK(const Point& p1, const Point& p2)
{
	if(p1.x != p2.x)
		return (p1.y - p2.y)/(p1.x - p2.x*1.0);
	else
		return numeric_limits<double>::max();
}

/** 
  * 寻找下一个顶点，即顺时针旋转遇到的第一个点
  * 若是上半部分，点应在右上侧；若是下半部分，点应在左下侧，通过locationDir函数判断
  */ 
Point findNextPoint(const Point& start, const vector<Point> & points, 
	bool (*locationDir)(const Point&, const Point&))
{
	double maxk = -numeric_limits<double>::max();
	Point nextPoint;
	for (vector<Point>::const_iterator it = points.begin(); it!=points.end(); ++it)
	{
		if(locationDir(start,*it))
		{
			// 计算斜率K值，double k = (it->y - start.y*1.0)/(it->x - start.x*1.0);			 
			double k = calculateK(*it, start);
			if(k > maxk)
			{
				maxk = k;
				nextPoint = *it;
			}
			else if(k == maxk && locationDir(nextPoint,*it))
			{
				// 去掉同一斜率的点，只保留其最外边的点
				maxk = k;
				nextPoint = *it;
			}
		}
	}
	return nextPoint;
}

// 打印找到的最大凸多边形
void printPoints(const vector<Point> & result)
{
	for(vector<Point>::const_iterator it=result.begin(); it!=result.end(); ++it)
	{
		cout<<it->x<<","<<it->y;
		if(it != result.end()-1)
			cout<<";";
	}
	cout<<endl;
}

// 读取输入的顶点信息，返回最左边点(left_out)和最右边的点(right_out)
void readPoints(vector<Point> & points, Point& left_out, Point& right_out)
{
	int n = 0; char ch;
	int x, y;
	cin>>n>>ch;
	for(int i=0; i<n; ++i)
	{
		cin>>x>>ch>>y;
		if(i != n-1)
			cin>>ch;
		Point point(x,y);
		points.push_back(point);
		if(i == 0)
			left_out = right_out = point;
		if(point < left_out)
			left_out = point;
		if(point > right_out)
			right_out = point;
	}
}

int main()
{
	vector<Point> points, result;
	Point left, right;
	// 读取点信息，并获取最左边和最右边的两个临界点
	readPoints(points, left, right);
	
	// 存入起点
	result.push_back(left);
	// 寻找右上方的点
	Point next = findNextPoint(left,points,isRightUpPoint);
	while(next != right)
	{
		result.push_back(next);
		next = findNextPoint(next,points,isRightUpPoint);
	}
	// 存入最右边的点
	result.push_back(right);
	// 寻找左下方的点
	next = findNextPoint(right,points,isLeftLowPoint);
	while(next != left)
	{
		result.push_back(next);
		next = findNextPoint(next,points,isLeftLowPoint);
	}

	printPoints(result);
	
	return 0;
}