本文主要是介绍NYOJ 78 圈水池（ 凸包入门），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：click here
题目：有一个牧场，牧场上有很多个供水装置，现在牧场的主人想要用篱笆把这些供水装置圈起来，以防止不是自己的牲畜来喝水，各个水池都标有各自的坐标，现在要你写一个程序利用最短的篱笆将这些供水装置圈起来！（篱笆足够多，并且长度可变）
输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出
- 样例输入
-
1 4 0 0 1 1 2 3 3 0
样例输出 -
0 0 2 3 3 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;
}
这篇关于NYOJ 78 圈水池（ 凸包入门）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
