判断凸包

2024-06-16 05:18
文章标签 判断 凸包

本文主要是介绍判断凸包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

下面以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.}  


                                    

这篇关于判断凸包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1065547

相关文章

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

判断PyTorch是GPU版还是CPU版的方法小结

《判断PyTorch是GPU版还是CPU版的方法小结》PyTorch作为当前最流行的深度学习框架之一,支持在CPU和GPU(NVIDIACUDA)上运行,所以对于深度学习开发者来说,正确识别PyTor... 目录前言为什么需要区分GPU和CPU版本?性能差异硬件要求如何检查PyTorch版本?方法1:使用命

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D