2015年百度之星程序设计大赛 - 初赛(1) 1006
题目链接：HDU 5251
Problem Description
Input
Output
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;
}