poj 2187 Beauty Contest(凸包求解多节点的之间的最大距离)
节点 最大 之间 poj 距离 求解 Contest 凸包
2023-09-27 14:20:24 时间
1 /* poj 2187 Beauty Contest 2 凸包:寻找每两点之间距离的最大值 3 这个最大值一定是在凸包的边缘上的! 4 5 求凸包的算法: Andrew算法! 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<cstring> 10 #include<algorithm> 11 using namespace std; 12 13 struct Point{ 14 Point(){} 15 Point(int x, int y){ 16 this->x=x; 17 this->y=y; 18 } 19 int x, y; 20 21 static int cross(Point a, Point b){ 22 return a.x*b.y - a.y*b.x; 23 } 24 25 static int dist(Point a, Point b){ 26 return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); 27 } 28 29 Point operator -(Point tmp){ 30 return Point(x-tmp.x, y-tmp.y); 31 } 32 }; 33 34 bool cmp(Point a, Point b){ 35 if(a.x==b.x) 36 return a.y<b.y; 37 return a.x<b.x; 38 } 39 40 Point p[50005]; 41 int ch[50005]; 42 int n; 43 44 int main(){ 45 int i; 46 while(scanf("%d", &n)!=EOF){ 47 for(i=0; i<n; ++i) 48 scanf("%d%d", &p[i].x, &p[i].y); 49 sort(p, p+n, cmp); 50 int m=0; 51 //求下凸包, 如果某一个点不在线段之内,向量的叉积必定是<=0; 52 for(i=0; i<n; ++i){ 53 while(m>1 && Point::cross(p[ch[m-1]]-p[ch[m-2]], p[i]-p[ch[m-2]])<=0) m--; 54 ch[m++]=i; 55 } 56 //为啥求上凸包的时候,坐标的从n-2开始:因为n-1点一定是在下凸包中的(因为它的横坐标最大,必然是包含其他节点的) 57 int k=m; 58 for(i=n-2; i>=0; --i){ 59 while(m>k && Point::cross(p[ch[m-1]]-p[ch[m-2]], p[i]-p[ch[m-2]])<=0) m--; 60 ch[m++]=i; 61 } 62 --m; 63 int maxD=-1, j, d; 64 for(i=0; i<m; ++i) 65 for(j=i+1; j<=m; ++j) 66 if(maxD < (d=Point::dist(p[ch[i]], p[ch[j]]))) 67 maxD=d; 68 printf("%d\n", maxD); 69 } 70 return 0; 71 }
相关文章
- Mnogo单节点 Docker模式安装
- 单节点安装Elasticsearch
- 【算法】【链表模块】单链表删除指定值节点
- el-tree节点模拟双击事件
- 求二叉树中,包含的最大二叉搜索子树的节点数量是多少
- 经典面试题:请你统计二叉树的最大宽度,即某一层节点数目最大值
- consul配置acl:允许注册和访问所有节点,并读取任何服务
- Elasticsearch节点,集群,分片及副本详解
- ROS机器人程序设计(原书第2版)3.2.3 为特定节点配置调试信息级别
- 二叉树——求最大节点和最小节点
- Linux(centos7)如何部署ElasticSearch7.6.2单节点跟集群(es部署指南)
- jQuery 获取当前节点的html包含当前节点的方法
- HDFS概念名称节点和数据节点-名称节点-文件系统元数据的持久状态
- JS DOM节点(当前标签和同级、父级、子级..之间的关系)
- 分布式技术EJB3_分库架构 - 【动力节点官网】北京Java …
- 6、多节点集群环境下Kafka的Confluent Platform的下载安装配置手册
- 华为OD机试 - 最小叶子节点(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 关于Cocos2d-x中精灵节点的透明度的设置
- [CareerCup] 13.7 Node Pointer 节点指针
- [CareerCup] 4.6 Find Next Node in a BST 寻找二叉搜索树中下一个节点