本文主要是介绍判断凸包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
下面以hdu2108为例,说明一下判断凸包的算法。
直接贴此题代码: 232K+15MS
#include <stdio.h>
#include <stdlib.h>
#define Max 1010
typedef struct Point{
int x;
int y;
}point;
point node[Max];
int n;
int det(int x1,int y1,int x2,int y2){
return x1*y2-x2*y1;
}
int cross(point A,point B,point C,point D){
return det(B.x-A.x,B.y-A.y,D.x-C.x,D.y-C.y);
}
bool Is_covbag(){
for(int i=0;i<=n-1;i++)
if(cross(node[i],node[i+1],node[i+1],node[i+2])<0)
return false;
return true;
}
int main(){
while(scanf("%d",&n),n){
if(n<3)
printf("concave\n");
else{
for(int i=1;i<=n;i++)
scanf("%d%d",&node[i].x,&node[i].y);
node[0].x=node[n].x,node[0].y=node[n].y;
node[n+1].x=node[1].x,node[n+1].y=node[1].y;
if(Is_covbag())
printf("convex\n");
else
printf("concave\n");
}
}
return 0;
}
<span style="font-family:Arial;BACKGROUND-COLOR: #ffffff">下面是更一般的算法模板:</span>
<pre class="cpp" name="code">01.#include<stdio.h>
02.#include<stdlib.h>
03.#include<math.h>
04.#define eps 1e-6 // 最小精度限制
05.#define Max 1010 // 设置最大多边形顶点个数
06.#define PI 3.141592654 //PI尽可能精度取高
07.typedef struct Point{ // 点结构
08. double x;
09. double y;
10.}point;
11.point node[Max];
12.point cir; // 圆坐标
13.int n;
14.double cirr; //圆半径
15.int dblcmp(double x){ // 判断正负零函数,一般double类型数据做加减法且要进行判断时,都要用到
16. if(fabs(x)<eps)
17. return 0;
18. return x>0?1:-1;
19.}
20.double dotdet(double x1,double y1,double x2,double y2){ // 计算点积(x1,y1)点积(x2,y2)
21. return x1*x2+y1*y2;
22.}
23.double det(double x1,double y1,double x2,double y2){ // 计算叉积 (x1,y1)叉积(x2,y2)
24. return x1*y2-x2*y1;
25.}
26.double cross(point A,point B,point C,point D){ // 计算叉积,AB叉积CD
27. return det(B.x-A.x,B.y-A.y,D.x-C.x,D.y-C.y);
28.}
29.double dist(point A,point B){ 计算点A与B距离
30. return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
31.}
32.double angle(point A,point B){ // 计算圆心与点A、B构成三角形的角度,圆心的角度
33. return acos(dotdet(A.x-cir.x,A.y-cir.y,B.x-cir.x,B.y-cir.y)/(dist(A,cir)*dist(B,cir)));
34.}
35.bool Is_covbag(){ //判断多边形是否为凸包,其中node可顺时针存放顶点也可逆时针存放顶点
36. int dir=0;
37. for(int i=0;i<=n-1;i++){
38. int temp=dblcmp(cross(node[i],node[i+1],node[i+1],node[i+2]));
39. if(dir==0) //第一次不为0,赋值
40. dir=temp;
41. if(dir*temp<0) //若和第一次的方向不同,说明不是凸包
42. return false;
43. }
44. return true; //为凸包
45.}
这篇关于判断凸包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!