题意

求凸包

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

最新文章

  1. Entity Framework 5.0系列之Code First数据库迁移
  2. Android中的四种动画(一)
  3. set gameobject Icons by Script
  4. FL2440移植Linux2.6.33.7内核
  5. 用户组,AD域控简介
  6. extjs中grid中行内文本或图片居中显示
  7. 今天聊一聊nuxt.js(上)
  8. Error when sending message to topic test with key: null, value: 2 bytes with error: (org.apache.kafka.clients.producer.internals.ErrorLoggingCallback)
  9. locust 参数,数据详解
  10. 【Netty源码分析】Netty服务端bind端口过程
  11. 为什么使用SLF4J?
  12. 上传本地文件到GitHub上
  13. Navicat Premium 12
  14. c/c++ 标准顺序容器 之 push_back,push_front,insert,emplace 操作
  15. D - Milking Time 动态规划
  16. Android开发(十八)——头部、中部、底部布局技巧
  17. 8 Ways to Become a Better Coder
  18. 冲刺Two之站立会议4
  19. BZOJ 2668 [cqoi2012]交换棋子 | 最小费用最大流
  20. hadoop学习笔记(九):MapReduce程序的编写

热门文章

  1. POJ3414 Pots —— BFS + 模拟
  2. [推荐]Silverlight 2 开发者海报
  3. Android中的ProgressBar的android:indeterminate
  4. TRIZ发明问题解决理论——本质是分析问题中的矛盾,利用资源(时间空间物质能量功能信息等)来解决矛盾从而解决问题——抽象出来:问题是什么,为什么?
  5. IDEA下搭建简单的SpringBoot工程应用
  6. [SoapUI] Jenkins 配置不同环境(TP, LIVE)
  7. 「LuoguP1799」 数列_NOI导刊2010提高(06)
  8. http基础知识摘录
  9. NOI前总结:点分治
  10. EasyUI 扩展自定义EasyUI校验规则 验证规则(常用的)