洛谷P2742 【模板】二维凸包
2024-08-30 13:11:54
题意
求凸包
Sol
Andrew算法:
首先按照$x$为第一关键字,$y$为第二关键字从小到大排序,并删除重复的点
用栈维护凸包内的点
1、把$p_1, p_2$放入栈中
2、若$p_{i{(i > 3)}}$在直线$p_{i - 1}, p_{i - 2}$的右侧,则不断的弹出栈顶,直到该点在直线左侧
3、此时我们已经得到了下凸包,那么反过来从$p_n$再做一次即可得到下凸包
这里主要是更新一下模板
// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int eps = 1e-;
int dcmp(double x) {
if(fabs(x) < eps) return ;
return x < ? - : ;
}
#define Point Vector
struct Vector {
double x, y;
Vector(double x = , double y = ) : x(x), y(y) {};
bool operator < (const Vector &rhs) const {
return dcmp(x - rhs.x) == ? y < rhs.y : x < rhs.x;
}
Vector operator - (const Vector &rhs) const {
return Vector(x - rhs.x, y - rhs.y);
}
};
double Cross(Vector A, Vector B) {
return A.x * B.y - A.y * B.x;
}
double dis(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int N;
Point p[], q[];
int top;
void Push(Point p) {
while(Cross(q[top] - q[top - ], p - q[top - ]) < ) top--;
q[++top] = p;
}
void Andrew() {
q[] = q[top = ] = p[];
for(int i = ; i <= N; i++) Push(p[i]);
for(int i = N - ; i; --i) Push(p[i]);
}
int main() {
scanf("%d", &N);
for(int i = ; i <= N; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + , p + N + );
Andrew();
double ans = ;
for(int i = ; i < top; i++)
ans += dis(q[i], q[i + ]);
printf("%.2lf", ans);
return ;
}
最新文章
- Entity Framework 5.0系列之Code First数据库迁移
- Android中的四种动画(一)
- set gameobject Icons by Script
- FL2440移植Linux2.6.33.7内核
- 用户组,AD域控简介
- extjs中grid中行内文本或图片居中显示
- 今天聊一聊nuxt.js(上)
- Error when sending message to topic test with key: null, value: 2 bytes with error: (org.apache.kafka.clients.producer.internals.ErrorLoggingCallback)
- locust 参数,数据详解
- 【Netty源码分析】Netty服务端bind端口过程
- 为什么使用SLF4J?
- 上传本地文件到GitHub上
- Navicat Premium 12
- c/c++ 标准顺序容器 之 push_back,push_front,insert,emplace 操作
- D - Milking Time 动态规划
- Android开发(十八)——头部、中部、底部布局技巧
- 8 Ways to Become a Better Coder
- 冲刺Two之站立会议4
- BZOJ 2668 [cqoi2012]交换棋子 | 最小费用最大流
- hadoop学习笔记(九):MapReduce程序的编写
热门文章
- POJ3414 Pots —— BFS + 模拟
- [推荐]Silverlight 2 开发者海报
- Android中的ProgressBar的android:indeterminate
- TRIZ发明问题解决理论——本质是分析问题中的矛盾,利用资源(时间空间物质能量功能信息等)来解决矛盾从而解决问题——抽象出来:问题是什么,为什么?
- IDEA下搭建简单的SpringBoot工程应用
- [SoapUI] Jenkins 配置不同环境(TP, LIVE)
- 「LuoguP1799」 数列_NOI导刊2010提高(06)
- http基础知识摘录
- NOI前总结:点分治
- EasyUI 扩展自定义EasyUI校验规则 验证规则(常用的)