判断凸包

全栈程序员-站长 • 2026年3月17日下午6:43 • 未分类 • 阅读 2

判断凸包下面以 hdu2108 为例说明一下判断凸包的算法

下面以hdu2108为例，说明一下判断凸包的算法。

直接贴此题代码： 232K+15MS

#include 
  
    #include 
   
     #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; }

下面是更一般的算法模板：

01.#include 
   
     02.#include 
    
      03.#include 
     
       04.#define eps 1e-6 // 最小精度限制 05.#define Max 1010 // 设置最大多边形顶点个数 06.#define PI 3. //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) 
      
        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.} 
       
      
     
   

 



                                                        版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/221186.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

上一篇 2026年3月17日下午6:43

Python locals() 的陷阱

下一篇 2026年3月17日下午6:43

SECS/GEM通信

SECS/GEM通信1 将 Secs dll secs h Secs lib 导入工程中 2 定义服务器和客户端的

全栈程序员-站长
2026年1月29日
2
Xsrf 验证

Xsrf 验证#!/usr/bin/envpython#-*-coding:utf-8-*-importtornado.ioloopimporttornado.webcontainer={}classSession:def__init__(self,handler):self.handler=handler…

全栈程序员-站长
2022年5月19日
47
访问数据库使用redis作为mysql的缓存（redis和mysql结合）

访问数据库使用redis作为mysql的缓存（redis和mysql结合）首先声明一下，我是在一个SSM项目的基础上进行优化的，所以就不进行基础的介绍了。下面我也补充一些知识点：redis：内存型数据库，有持久化功能，具备分布式特性，可靠性高，适用于对读写效率要求都很高，数据处理业务复杂和对安全性要求较高的系统（如新浪微博的计数和微博发布部分系统，对数据安全性、读写要求都很高）。缓存机制说明：所有的查询结果都放进了缓存，也就是把MySQL查询的结果放…

全栈程序员-站长
2022年6月17日
38
Tomcat面试题+http面试题+Nginx面试题+常见面试题

Tomcat面试题+http面试题+Nginx面试题+常见面试题Tomcat面试题1、Tomcat的缺省端口是多少？怎么修改？答：缺省端口是8080，若要修改，可以进入Tomcat的安装目录下找到conf目录下的server.xml文件，找到该文件中的Connector字段中的port。2、Tomcat有哪几种connector运行模式（服务的请求方式）？答：三种。修改它的运行模式需要在主配置文件中找到connector字段中的protocol进行修改…

全栈程序员-站长
2022年5月29日
29
Midjourney

Midjourney平替本地部署全指南

Midjourney平替本地部署全指南

全栈程序员-站长
2026年3月15日
2
推荐10个堪称神器的学习网站

推荐10个堪称神器的学习网站每天都会收到很多读者的私信，问我：“二哥，有什么推荐的学习网站吗？最近很浮躁，手头的一些网站都看烦了，想看看二哥这里有什么新鲜货。”今天一早做了个恶梦，梦到被老板辞退了。虽然说在我们公司，只有我辞退老板的份，没有老板辞退我这一说，但是还是被吓得4点多都起来了。（主要是因为我掌握着公司所有的核心源码，哈哈哈）既然4点多起来，就得好好利用起来。于是我就挑选了10个堪称神器的学习网站，推…

全栈程序员-站长
2022年6月9日
51

发表回复

关注全栈程序员社区公众号