计算几何:凸包（圈水池）

计算几何:凸包（圈水池）

这是最简单的凸包入门题。

解决这样的问题两个出名的算法。

一、  Graham扫描法，运行时间为O(nlgn)。

二、  Jarvis步进法，运行时间为O(nh),h为凸包中的顶点数。

圈水池

3000 ms  |  内存限制： 65535

4

第一行输入的是N,代表用N组测试数据（1<=N<=10）

第二行输入的是m,代表本组测试数据共有m个供水装置（3<=m<=100）

接下来m行代表的是各个供水装置的横纵坐标

输出 输出各个篱笆经过各个供水装置的坐标点，并且按照x轴坐标值从小到大输出，如果x轴坐标值相同，再安照y轴坐标值从小到大输出 样例输入

140 01 12 33 0

样例输出

0 02 33 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#include#includeusing namespace std;struct point { int x,y;}pnt[105],res[105];bool cmp(const point &p1,const point &p2){ return p1.x(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=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>pnt[i].x>>pnt[i].y; j=graham(pnt,m,res); sort(res,res+j,cmp); for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。