链接：click here
题目：有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）
输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出
样例输入140 01 12 33 0样例输出0 02 33 0
凸包Graham模板:详细讲解：click here
第一步:选取x轴坐标最小的点,如果存在多个选y轴坐标最小的点.第二步:排序.从下到上扫描有其它点扫描的结果顺序,p0, p4, p5, p7, p9,p6, p8, p2,p3, p1.数学公式向量的外积模公式:|c|(是模不是绝对值符号)= |a|*|b|*sin<a, b> = a.x * b.y – b.x * a.y|c|> 0:向量a在向量b的顺时针方向,因为此例原点坐标取x轴坐标最小的点,所以,向量a在向量b的下方.(p0-p4线段在p0-p5的下方).|c|= 0:共线时,按照与原点距离由小到大的顺序.第三步:按照第二步得到的顶点顺序进行graham扫描.按照本例选取的原点方式,当扫描到左拐(p0,p4, p5)时保留(p4),右拐(p9,p6, p8)时删除顶点(p6),结果就是凸包的顶点集.(绿线扫描的顺序，红线为左拐点).共线时,删除距离较小的点.注意：右拐删除结点时,必须回溯与前面保留的点重新比较,因为删除一个点后先前拐点性质会发生变化
参考自博客：click here
代码：
#include <stdio.h> //凸包Graham模板#include <stdlib.h>#include <string.h>#include <queue>#include <math.h>#include <deque>#include <algorithm>#include <iostream>using namespace std;const double eps=1e-6;const int maxn=105;const int inf=0x3f3f3f3f;const double pi=acos(-1.0);struct point{int x,y;};point rec1[maxn],rec2[maxn];int stack[maxn],top;int cross(point p0,point p1,point p2) //计算叉积 p0p1 X p0p2 {return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}double dis(point p1,point p2) //计算 p1p2的 距离 /{return sqrt((double) (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));}bool cmp1(point p1,point p2)//极角排序函数 ， 角度相同则距离小的在前面 {int trap=cross(rec1[0],p1,p2);if(trap>0) return true;else if (trap==0&&dis(rec1[0],p1)<dis(rec1[0],p2)) return true;else return false;}bool cmp2(const point &p1,const point &p2){return p1.x==p2.x?p1.y<p2.y:p1.x<p2.x;}void input(int n) //输入，并把 最左下方的点放在 list[0] 并且进行极角排序 {int i,j,k,l;point p0;scanf("%d%d",&rec1[0].x,&rec1[0].y);p0.x=rec1[0].x;p0.y=rec1[0].y;k=0;for(i=1; i<n; i++){scanf("%d%d",&rec1[i].x,&rec1[i].y);if((p0.y>rec1[i].y)||((p0.y==rec1[i].y)&&(p0.x>rec1[i].x))){p0.x=rec1[i].x;p0.y=rec1[i].y;k=i;}}rec1[k]=rec1[0];rec1[0]=p0;sort(rec1+1,rec1+n,cmp1);}void graham(int n){int i;if(n==1) {top=0;stack[0]=0;}if(n==2) {top=1;stack[0]=0;stack[1]=1;}if(n>2){stack[0]=0,stack[1]=1;top=1;for(i=2; i<n; i++){while(top>0&&cross(rec1[stack[top-1]],rec1[stack[top]],rec1[i])<=0) top–;top++;stack[top]=i;}}}int main(){int i,j,t,m,n;scanf("%d",&t);while(t–){scanf("%d",&m);input(m);graham(m);double res=0;for(i=0; i<=top; i++){rec2[i].x=rec1[stack[i]].x;rec2[i].y=rec1[stack[i]].y;}sort(rec2,rec2+top+1,cmp2);for(i=0; i<=top; i++)printf("%d %d\n",rec2[i].x,rec2[i].y);}return 0;}
玩坏了可以选择重来，
