B. Concave Hull
题目描述
简单多边形是平面中由线段组成的闭合曲线,这些线段首尾相连,除了因连接共用的线段端点,任何两
个线段都不能彼此相交。
简单多边形可以分为两类:凸多边形和凹多边形。一个凸多边形是指:多边形中任意两点间的线段上的
所有点都在多边形内,包括在内部或边界上。不是凸多边形的简单多边形就是凹多边形。如图,左边
是一个凸多边形,右边是一个凹多边形。
现在,给定 n 个点,满足所有点互不相同,且不存在三个点在同一条直线上。你的任务是选择这 n 个点
中的一些点(可以全选),并按照任意顺序依次连边,最后需要连成一个面积严格大于 0 的凹多边形。
你需要求出能形成的凹多边形的面积最大是多少。
输入描述
第一行一个正整数 \(T\) \((1 \leq T \leq 10^4)\),表示数据组数。
对于每组数据,第一行一个正整数 \(n\) \((3 \leq n \leq 10^5)\),表示点数。
接下来 \(n\) 行,每行两个整数 \(x_i\), \(y_i\) \((−10^9 \leq x_i, y_i \leq 10^9)\),表示各个点的坐标。保证所有点的坐标互不相
同,且不存在三点共线。
各个测试数据组的 \(n\) 之和不超过 \(2 · 10^5\)。
输出描述
对于每组数据,如果不能形成面积严格大于 \(0\) 的凹多边形,输出 \(−1\);否则,输出一个正整数,表示形成的最大的凹多边形的面积的两倍。可以证明这个答案是一个正整数。
解题思路
对于凸多边形来说,显然凸包就是答案,而凹多边形的最大面积显然就是将凸包上的某一点由凸变凹(去掉那个小三角形),也就是枚举凸包上的边并找到离这个边最近的点,直接暴力枚举会超时,但是不难发现这些点都有个特征:它们都位于去除构成凸包的点后,剩余点构成的凸包上,因此双指针扫描一遍即可。
代码实现
#include <bits/stdc++.h>
#define int long long
struct Point {
int x, y;
bool operator<(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
bool operator==(const Point &p) const {
return x == p.x && y == p.y;
}
};
// 向量叉积求三点面积的两倍
int cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// andrew构建凸包
std::vector<Point> andrew(std::vector<Point> points) {
std::sort(points.begin(), points.end());
std::vector<Point> hull;
// 需要特判一下剩余点集不能构成封闭图形的情况
if (points.size() <= 2) {
return points;
}
for (int i = 0; i < 2; i++) {
int st = hull.size();
for (const auto p: points) {
while (hull.size() >= st + 2 && cross(hull[hull.size() - 2], hull.back(), p) <= 0) {
hull.pop_back();
}
hull.push_back(p);
}
hull.pop_back();
std::reverse(points.begin(), points.end());
}
if (hull.size() > 1 && hull.front() == hull.back()) {
hull.pop_back();
}
return hull;
}
// 求凸包面积
int area(const std::vector<Point> &points) {
int res = 0;
int n = points.size();
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
res += points[i].x * points[j].y - points[j].x * points[i].y;
}
return std::abs(res);
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
std::vector<Point> points1(n), points2;
for (int i = 0; i < n; i++) {
std::cin >> points1[i].x >> points1[i].y;
}
// 构建外层凸包
std::vector<Point> hull1 = andrew(points1), hull2;
std::set<Point> st;
for (auto p: hull1) {
st.insert(p);
}
for (auto p: points1) {
if (!st.count(p)) {
points2.push_back(p);
}
}
// 构建内层凸包
hull2 = andrew(points2);
// 特判点集只能构成凸包
if (hull2.size() == 0) {
std::cout << -1 << "\n";
continue;
}
int pos = 0, min1 = 4e18, siz1 = hull1.size(), siz2 = hull2.size();
Point p1 = hull1[0], p2 = hull1[1];
for (int i = 0; i < siz2; i++) {
Point p3 = hull2[i];
if (cross(p1, p2, p3) < min1) { // 初始化需要去掉的最小面积并记录位置
min1 = cross(p1, p2, p3);
pos = i;
}
}
// 末尾防越界直接开两倍
for (int i = 0; i < siz2; i++) {
hull2.push_back(hull2[i]);
}
siz2 = hull2.size();
int lastpos = pos; // 上一次最小的位置
for (int i = 1; i < siz1; i++) {
p1 = hull1[i], p2 = hull1[i + 1]; // 枚举外层凸包上的点
lastpos = pos;
int min2 = 4e18;
while (lastpos < siz2) { // 枚举内层凸包上的点
Point p3 = hull2[lastpos];
if (min2 > cross(p1, p2, p3)) {
min2 = cross(p1, p2, p3);
min1 = std::min(min1, min2); // 更新最小值和位置
pos = lastpos;
lastpos++;
} else {
break;
}
}
}
std::cout << area(hull1) - min1 << "\n";
}
}
标签:std,多边形,int,hull,Site,CCPC,2024,leq,points
From: https://www.cnblogs.com/udiandianis/p/18530817