洛谷P2742 圈奶牛 (凸包 Andrew算法)

embedded/2024/12/21 10:51:53/

[USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

题目背景

upd: 新增一组 hack 数据。

题目描述

农夫约翰想要建造一个围栏用来围住他的奶牛,可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标,计算最短的能够围住这些点的围栏的长度。

输入格式

输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 n n n

2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行,每行两个实数,第 ( i + 1 ) (i + 1) (i+1) 行的实数 x i , y i x_i, y_i xi,yi 分别代表第 i i i 个放牧点的横纵坐标。

输出格式

输出输出一行一个四舍五入保留两位小数的实数,代表围栏的长度。

样例 #1

样例输入 #1

4
4 8
4 12
5 9.3
7 8

样例输出 #1

12.00

提示

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105 − 1 0 6 ≤ x i , y i ≤ 1 0 6 -10^6 \leq x_i, y_i \leq 10^6 106xi,yi106。小数点后最多有 2 2 2 位数字。

思路

Convex_hull()函数求凸包,用unique()函数去重

#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1e5 + 5;
const double eps = 1e-6;int sgn(double x) {if (fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;
}struct Point {double x, y;Point() {}Point(double x, double y) : x(x), y(y) {}Point operator + (Point B){return Point(x + B.x, y + B.y);}Point operator - (Point B){return Point(x - B.x, y - B.y);}Point operator * (double k) {return Point(x * k, y * k);}Point operator / (double k) {return Point(x / k, y / k);}bool operator == (Point B) {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}// 按x坐标从小到大排序 若x坐标相同 按y坐标从小到大排序bool operator < (Point B) {return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);}
};typedef Point Vector;double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;
}double Dist(Point A, Point B) {return hypot(A.x - B.x, A.y - B.y);
}int Convex_hull(Point *p, int n, Point *ch) {n = unique(p, p + n) - p; // 去除重复点sort(p, p + n);int v = 0;// 求下凸包 如果p[i]右拐弯 这个点不在凸包上 回退for (int i = 0; i < n; ++i) {while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)v--;ch[v++] = p[i];}int j = v;// 求上凸包for (int i = n - 2; i >= 0; --i) {while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)--v;ch[v++] = p[i];}if (n > 1) --v; // 在构造上凸包时,最后一个点和第一个点是重复的,因此我们需要减去 1,以确保没有重复的点。return v;
}Point p[N], ch[N];
void solve() {int n; cin >> n;for (int i = 0; i < n; ++i) {scanf("%lf %lf", &p[i].x, &p[i].y);}int v = Convex_hull(p, n, ch); // 返回凸包顶点数double ans = 0;for (int i = 0; i < v; ++i) {ans += Dist(ch[i], ch[(i + 1) % v]);}printf("%.2f\n", ans);
}int main() {int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}

http://www.ppmy.cn/embedded/147510.html

相关文章

最新D音滑块JS纯算法还原(含完整源码)

文章目录 1. 写在前面2. 接口分析2. 源码实现【🏠作者主页】:吴秋霖 【💼作者介绍】:擅长爬虫与JS加密逆向分析!Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python与爬虫领域研究与开发工作! 【🌟作者推荐】:对爬…

RIP协议的数据包

RIP协议的数据包 Request--请求包 Response---应答包 流程 1.设备首次启动RIP协议后&#xff0c;会向所有的直连接口发送request包&#xff0c;用来请求邻居发送路由信 息 2.其他设备收到请求包后&#xff0c;会利用response包传递路由信息 3.设备收到response包后&#…

STM32-笔记6-震动控制灯(中断法)

1、复制06工程文件&#xff0c;重命名07-震动控制灯&#xff08;中断法&#xff09; 打开工程文件 打开exti.c文件 将震动传感器的DO口接32板的A4引脚 更改代码 2、代码&#xff08;老师的&#xff09; exti.c #include "sys.h" #include "exti.h" …

专业125+总分400+南京理工大学818考研经验南理工电子信息与通信工程,真题,大纲,参考书。

考研成功上岸&#xff0c;苦尽甘来&#xff0c;专业818信号系统与数字电路125&#xff0c;总分400&#xff0c;被南理工录取&#xff0c;从最早信心满满&#xff0c;到中期犹豫不决&#xff0c;到后期破釜沉舟&#xff0c;一路颠颠簸簸&#xff0c;总算坚持过来了&#xff0c;群…

使用 Lambda 创建 Authorizer 对 API Gateway 访问进行鉴权

背景介绍 对于配置好的 API Gateway 资源来说, 默认会允许所有客户端进行访问. 我们可以配置 API key 进行简单的访问控制, 不过需要注意, API key 主要应用场景其实还是结合 Usage plan 对访问量进行控制, 并不提供鉴权的目的. 毕竟 API key 会作为一个静态的 Header x-api-k…

方正畅享全媒体新闻采编系统 screen.do SQL注入漏洞复现

0x01 产品简介 方正畅享全媒体新闻生产系统是以内容资产为核心的智能化融合媒体业务平台,融合了报、网、端、微、自媒体分发平台等全渠道内容。该平台由协调指挥调度、数据资源聚合、融合生产、全渠道发布、智能传播分析、融合考核等多个平台组成,贯穿新闻生产策、采、编、发…

【功能安全】硬件架构度量

目录 01 硬件架构度量介绍 02 硬件架构度量相关说明 03 硬件架构度量示例 04 硬件架构度量模板 01 硬件架构度量介绍 GBT 34590 2022 part5

网络协议与网络安全学习记录

SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全&#xff08;Transport Layer Security&#xff0c;TLS&#xff09;是为网络通信提供安全及数据完整性的一种安全协议。TLS与SSL在传输层对网络连接进行加密 HTTPS,代表Hyper Text Transfer Protocol Secure,将SSL/T…