二维凸包-P2742-学习笔记-解题报告
i207M
·
·
题解
题意
维护一个完整的二维凸包；
实现
我们先回顾一下叉积的性质：
**$|a×b|$的值就为以a，b为边构成平行四边形的面积；**
叉积的运用（凸包和极角排序会用用到）：
**$a×b>0$ 则说明 b在a的左上方；**
**$a×b<0$ 则说明b在a的右下方；**
我们要维护一个完整的凸包；
很明显我们要排序，我以x升序，y降序排列；
所以我们要把它分为上下两个部分（形象理解为两个半圆）；
一个单调队列维护斜率递减（上凸包）；
另一个维护斜率单调递增（下凸包）；
为了使其成为一个完整的凸包，我们要强制在两个里面塞进1和n点；
## 易错
注意判断上下两部分的时候一定要用叉积；
## 代码
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof(x))
#define mem1(x) memset((x),0x3f,sizeof(x))
#define gc getchar
template<class T>void in(T &x)
{
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
int n;
#define eps 1e-14
il bool isequ(const double &a, const double &b) {
return (a - b) <= eps && (a - b) >= -eps;
}
#define N 10010
struct Node {
double x, y;
Node() {}
Node(double xx, double yy) {
x = xx, y = yy;
}
friend bool operator<(const Node &a, const Node &b) {
if (isequ(a.x, b.x)) return a.y > b.y;
return a.x < b.x;
}
} nod[N];
double ans;
int up[N], cup;
int dow[N], cdow;
il Node det(const int &a, const int &b) {
return Node(nod[a].x - nod[b].x, nod[a].y - nod[b].y);
}
il bool cj(const Node &a, const Node &b) {
return (a.x * b.y - a.y * b.x) > 0.0;
}
il void pushup(const int &i) {
while (cup > 1 && cj(det(i, up[cup - 1]), det(up[cup], up[cup - 1])) == 0) {
--cup;
}
up[++cup] = i;
}
il void pushdow(const int &i) {
while (cdow > 1 && cj(det(i, dow[cdow - 1]), det(dow[cdow], dow[cdow - 1])) == 1) {
--cdow;
}
dow[++cdow] = i;
}
il double getd(const Node &a) {
return sqrt(a.x * a.x + a.y * a.y);
}
il double slope(const Node &a) {
return a.y / a.x;
}
signed main() {
in(n);
for (ri i = 1; i <= n; ++i)
scanf("%lf%lf", &nod[i].x, &nod[i].y);
sort(nod + 1, nod + 1 + n);
dow[++cdow] = up[++cup] = 1;
for (ri i = 2; i < n; ++i) {
if (cj(det(i, 1), det(n, 1)) == 0) {
pushup(i);
}
else {
pushdow(i);
}
}
pushup(n);
pushdow(n);
for (ri i = 1; i < cup; ++i) {
ans += getd(det(up[i], up[i + 1]));
}
for (ri i = 1; i < cdow; ++i) {
ans += getd(det(dow[i], dow[i + 1]));
}
printf("%.2f\n", ans);
return 0;
}
```