本文主要是介绍poj2187凸包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天复习了一下凸包，感觉对于它的理解又加深了，凸包注意的有几点：1基准点在最下面的最左边（习惯性的，注意不只是最下面）2，另外零要重新定义，不再只是一个数，而是一个范围，那么此时对于判零的一系列操作就要注意了，什么时候为右端点，什么时候为左端点，什么时候要进行判零操作等等，3叉乘，要注意与qsort的结合，不要搞混了。
下面是这题的代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
using namespace std;
#define maxn 50000
#define zero 1e-8
struct Point
{int x;int y;
}node[maxn];int n;
inline int Distance(const Point ,const Point );
int cmp(const void *,const void*);
int CJ(const Point,const Point,const Point);
bool Is_zero(double );
void TB(int );int main()
{scanf("%d",&n);int i,pivot;int below=maxn;for(i=0;i<n;i++){scanf("%d%d",&node[i].x,&node[i].y);if(node[i].y<below){below=node[i].y;pivot=i;}}for(i=0;i<n;i++){if(node[i].y==node[pivot].y && node[i].x<node[pivot].x)pivot=i;} Point temp;temp=node[0];node[0]=node[pivot];node[pivot]=temp;qsort(node+1,n-1,sizeof(Point),cmp);for(i=0;i<n;i++)cout << node[i].x << " " << node[i].y << endl;int k=1;for(i=2;i<n;i++){if(Is_zero(double(CJ(node[0],node[k],node[i])))){if(Distance(node[0],node[k])<Distance(node[0],node[i]))node[k]=node[i];}elsenode[++k]=node[i];}TB(k+1);return 0;
}
inline int Distance(const Point a,Point b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}int cmp(const void *p,const void*q){return CJ(node[0],*((Point*)p),*((Point *)q))>zero?1:-1;
}
int CJ(const Point s,const Point p,const Point q) //sq叉乘sp
{return (q.x-s.x)*(p.y-s.y)-(q.y-s.y)*(p.x-s.x);
}bool Is_zero(double x){return fabs(x)<=zero;
}
void TB(int m){node[m]=node[0];int i,j,k=2;for(i=3;i<=m;i++){while(CJ(node[k],node[k-1],node[i])<-zero)k--;node[++k]=node[i];}int temp=-maxn;int xpivot,ypivot;int ans;for(i=0;i<k;i++){for(j=0;j<k;j++){ans=Distance(node[i],node[j]);if(ans>temp){temp=ans;xpivot=i;ypivot=j;}}}printf("%d\n",(node[xpivot].x-node[ypivot].x) * (node[xpivot].x-node[ypivot].x) + (node[xpivot].y-node[ypivot].y) * (node[xpivot].y-node[ypivot].y) );
}
里面包含了凸包的模版，好好理解，特别是void TB（int m)中的while循环，注意与if的差别，以及主函数中的for循环，都是利用了：满足条件则进，不满足则退的思想，当然这不够准确，还是要自己慢慢思考才能理解....
这篇关于poj2187凸包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
