HDU 5251 矩形面积 (旋转卡壳)
2024-10-05 03:40:17
2015年百度之星程序设计大赛 - 初赛(1) 1006
题目链接:HDU 5251
Problem Description
小度熊有一个桌面,小度熊剪了很多矩形放在桌面上,小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。
Input
第一行一个正整数 \(T\),代表测试数据组数 \((1\le T\le 20)\),接下来 \(T\) 组测试数据。
每组测试数据占若干行,第一行一个正整数 \(N(1\le N\le 1000)\),代表矩形的数量。接下来 \(N\) 行,每行 \(8\) 个整数 \(x1,y1,x2,y2,x3,y3,x4,y4\),代表矩形的四个点坐标,坐标绝对值不会超过10000。
Output
对于每组测试数据,输出两行:
第一行输出"Case #i:",i 代表第 i 组测试数据。
第二行包含1 个数字,代表面积最小的矩形的面积,结果保留到整数位。
Sample Input
2
2
5 10 5 8 3 10 3 8
8 8 8 6 7 8 7 6
1
0 0 2 2 2 0 0 2
Sample Output
Case #1:
17
Case #2:
4
Solution
旋转卡壳
思路见这里:洛谷 P3187 BZOJ 1185 [HNOI2007]最小矩形覆盖 (旋转卡壳)
杭电就比较良心了,没有卡精度。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int maxn = 100000 + 5;
int n;
inline int dcmp(double x) {
if(fabs(x) < eps) return 0;
return x > 0? 1: -1;
}
class Point {
public:
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
Point operator+(Point a) {
return Point(a.x + x, a.y + y);
}
Point operator-(Point a) {
return Point(x - a.x, y - a.y);
}
bool operator<(const Point &a) const {
if (x == a.x)
return y < a.y;
return x < a.x;
}
Point operator*(double a) {
return Point(x * a, y * a);
}
bool operator==(const Point &a) const {
if (x == a.x && y == a.y)
return 1;
return 0;
}
double len() {
return sqrt(x * x + y * y);
}
double dis2(const Point a) {
return pow(x - a.x, 2) + pow(y - a.y, 2);
}
double dis(const Point a) {
return sqrt(dis2(a));
}
};
Point ans[10];
typedef Point Vector;
double cross(Vector a, Vector b) {
return a.x * b.y - a.y * b.x;
}
double dot(Vector a, Vector b) {
return a.x * b.x + a.y * b.y;
}
typedef vector<Point> Polygon;
Polygon Andrew(Polygon P) {
int n = P.size(), k = 0;
vector<Point> H(2 * n);
sort(P.begin(), P.end());
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(H[k - 1] - H[k - 2], P[i] - H[k - 2]) < eps) {
k--;
}
H[k++] = P[i];
}
int t = k + 1;
for (int i = n - 1; i > 0; --i) {
while (k >= t && cross(H[k - 1] - H[k - 2], P[i - 1] - H[k - 2]) < eps) {
k--;
}
H[k++] = P[i - 1];
}
H.resize(k - 1);
return H;
}
double rotating_caliper(Polygon v) {
double min_s = 1e18;
int cnt = v.size();
v.push_back(v[0]);
int u = 1, r = 1, l = 1;
for (int i = 0; i < cnt; ++i) {
// 最上面的点
while (dcmp(fabs(cross(v[u] - v[i], v[i + 1] - v[i])) - fabs(cross(v[u + 1] - v[i], v[i + 1] - v[i]))) <= 0) {
u = (u + 1) % cnt;
}
// 最右边的点
while (dcmp(dot(v[r] - v[i], v[i + 1] - v[i]) - dot(v[r + 1] - v[i], v[i + 1] - v[i])) <= 0) {
r = (r + 1) % cnt;
}
if(!i) l = r;
// 最左边的点
while (dcmp(dot(v[l] - v[i], v[i + 1] - v[i]) - dot(v[l + 1] - v[i], v[i + 1] - v[i])) >= 0) {
l = (l + 1) % cnt;
}
double d = v[i].dis(v[i + 1]);
double R = dot(v[r] - v[i], v[i + 1] - v[i]) / d;
double L = dot(v[l] - v[i], v[i + 1] - v[i]) / d;
double ll = R - L;
double dd = fabs(cross(v[u] - v[i], v[i + 1] - v[i])) / d;
min_s = min(min_s, ll * dd);
}
return min_s;
}
int main() {
int T;
scanf("%d", &T);
for(int _ = 1; _ <= T; ++_) {
scanf("%d", &n);
Polygon s;
for(int i = 0; i < n * 4; ++i) {
Point p;
scanf("%lf%lf", &p.x, &p.y);
s.push_back(p);
}
Polygon p = Andrew(s);
double d = rotating_caliper(p);
printf("Case #%d:\n%.0lf\n", _, d);
}
return 0;
}
最新文章
- 【原创】如何确定Kafka的分区数、key和consumer线程数
- OS X: Messages Agent wants to use the ";login"; keychain
- js判断当前的访问是手机/电脑
- eval 与 Function
- EF CodeFirst 如何通过配置自动创建数据库<;当模型改变时>;
- SqlMapConfig.xml中的setting属性设置
- STL源码分析读书笔记--第5章--关联式容器
- 从零开始学习Hadoop--第2章 第一个MapReduce程序
- XML&;nbsp; XmlDocument
- SGU 152.Making round
- Android之GPS应用开发
- oracle创建表空间-用户-角色-授权
- vim 多行注释
- java环境变量设置--编写一年java,竟不会配变量了
- Memory Analyzer Tool 使用手记
- VUE环境项目搭建以及简单的运行例子
- PAT A1010.Radix 二分法
- ABP-添加表
- Win10家庭版、专业版、企业版、教育版各版本功能区别对照表
- 升级cocoapods1.1.1版本