計算幾何:凸包（圈水池）

這是最簡單的凸包入門題。 解決這樣的問題兩個出名的算法。

一、  Graham掃描法，運作時間為O(nlgn)。

二、  Jarvis步進法，運作時間為O(nh),h為凸包中的頂點數。

圈水池

時間限制： 3000 ms  |  記憶體限制： 65535 KB 難度： 4

描述

有一個牧場，牧場上有很多個供水裝置，現在牧場的主人想要用籬笆把這些供水裝置圈起來，以防止不是自己的牲畜來喝水，各個水池都标有各自的坐标，現在要你寫一個程式利用最短的籬笆将這些供水裝置圈起來！（籬笆足夠多，并且長度可變）

輸入

第一行輸入的是N,代表用N組測試資料（1<=N<=10）

第二行輸入的是m,代表本組測試資料共有m個供水裝置（3<=m<=100）

接下來m行代表的是各個供水裝置的橫縱坐标

輸出

輸出各個籬笆經過各個供水裝置的坐标點，并且按照x軸坐标值從小到大輸出，如果x軸坐标值相同，再安照y軸坐标值從小到大輸出

樣例輸入

1
4
0 0
1 1
2 3
3 0
      

樣例輸出

0 0
2 3
3 0      

題解：

輸出各個籬笆經過各個供水裝置的坐标點， 從這句話可以得到，如果3點共線，那麼這3個點都要輸出。

 在叉積函數中  return (sp.x-op.x)*(ep.y-op.y)>(sp.y-op.y)*(ep.x-op.x);     即可解決。

凸包 中的叉積  return (sp.x-op.x)*(ep.y-op.y)>=(sp.y-op.y)*(ep.x-op.x);   在一條直線上的點取兩頭的，中間的不要。

注意一下這點，這道題就很簡單了。直接套用凸包即可解決。

AC代碼：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct point 
{
	int x,y;
}pnt[105],res[105];

bool cmp(const point &p1,const point &p2)
{
	return p1.x<p2.x||(p1.x==p2.x&&p1.y<p2.y);
}

bool mult(point sp,point ep,point op)
{
	return (sp.x-op.x)*(ep.y-op.y)>(sp.y-op.y)*(ep.x-op.x);
}

int graham(point pnt[],int n,point res[])
{
	int i,len,top;   top=1;
	sort(pnt,pnt+n,cmp);
	if(n==0) return 0; res[0]=pnt[0];
	if(n==1) return 1; res[1]=pnt[1];
	if(n==2) return 2; res[2]=pnt[2];
	for(i=2;i<n;i++)
	{
		while(top&&mult(pnt[i],res[top],res[top-1]))
			top--;
		res[++top]=pnt[i];
	}
	len=top;
	res[++top]=pnt[n-2];
	for(i=n-3;i>=0;i--)
	{
		while(top!=len&& mult(pnt[i],res[top],res[top-1]))
			top--;
		res[++top]=pnt[i];
	}
	return top;
}
int main()
{
	int N,m;
	cin>>N;
	while(N--)
	{
		cin>>m;
		int i,j;
		for(i=0;i<m;i++)
			cin>>pnt[i].x>>pnt[i].y;
		j=graham(pnt,m,res);
		sort(res,res+j,cmp);
		for(i=0;i<j;i++)
			cout<<res[i].x<<" "<<res[i].y<<endl;
	}
	return 0;
}