P4166 [SCOI2007]最大土地面积 题解
s_c_lmlm_L · · 题解
前置知识：矢量，平面凸包，旋转卡壳
平面凸包是指覆盖平面上
对已以上算法，万一斜率无穷大，即不能保证准确性，我们就得采用另一种算法，Jarvis 算法。
算法大体思想：形成凸包的构造函数是这样的，找到一条直线
#include<bits/stdc++.h>
const double eps = 1e-10;
inline int dcmp(const double &x) {
if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1;
}
namespace geometry {
using std::max;
using std::sort;
using std::unique;
struct point {
double x, y;
point(double x = 0, double y = 0) : x(x), y(y) { }
bool operator < (const point &b) const {
return x != b.x ? x < b.x : y < b.y;
}
};
typedef point vector;
typedef std::vector<point> polygon;
struct line {
point p; vector v; double ang;
line() {}
line(point p, vector v) : p(p), v(v) { ang = atan2(v.y, v.x);}
bool operator < (const line &b) const {
return ang < b.ang;
}
};
typedef std::vector<line> line_set;
vector operator + (const vector &A, const vector &B) { return point(A.x + B.x, A.y + B.y);}
vector operator - (const point &A, const point &B) { return point(A.x - B.x, A.y - B.y);}
vector operator * (const vector &A, const double &b) { return vector(A.x * b, A.y * b);}
vector operator / (const vector &A, const double &b) { return vector(A.x / b, A.y / b);}
bool operator == (const point &A, const point &B) { return fabs(A.x - B.x) < eps && fabs(A.y - B.y) < eps;}
inline double dot(const vector &A, const vector &B) { return A.x * B.x + A.y * B.y;}
inline double cross(const vector &A, const vector &B) { return A.x * B.y - A.y * B.x;}
inline double length(const vector &A) { return sqrt(dot(A, A));}
inline double angle(const vector &A, const vector &B) { return acos(dot(A, B) / length(A) / length(B));}
inline vector rotate(const vector &A, const double &rad) {
double c = cos(rad), s = sin(rad);
return vector(A.x * c - A.y * s, A.x * s + A.y * c);
}
inline vector normal(const vector &A) {
double L = length(A); return vector(-A.y / L, A.x / L);
}
inline bool on_left(line L, point p) {
return cross(L.v, p - L.p) > 0;
}
inline bool on_segment(point p, point a1, point a2) {
return dcmp(cross(a1 - p, a2 - p) == 0) && dcmp(dot(a1 - p, a2 - p)) < 0;
}
inline bool segment_proper_intersection(point a1, point a2, point b1, point b2) {
double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1),
c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
int in_polygon(point p, polygon &poly) {
int wn = 0;
for (int i = 0, n = poly.size(); i < n; i++) {
if (on_segment(p, poly[i], poly[i%n+1])) return -1;
int k = dcmp(cross(poly[i%n+1] - poly[i], p - poly[i]));
int d1 = dcmp(poly[i].y - p.y);
int d2 = dcmp(poly[i%n+1].y - p.y);
if (k > 0 && d1 <= 0 && d2 > 0) wn++;
if (k < 0 && d2 <= 0 && d1 > 0) wn--;
}
if (wn != 0) return 1;
return 0;
}
inline point line_intersection(point p, vector v, point q, vector w) {
vector u = p - q; double t = cross(w, u) / cross(v, w);
return p + v * t;
}
inline point line_intersection(line a, line b) {
vector u = a.p - b.p; double t = cross(b.v, u) / cross(a.v, b.v);
return a.p + a.v * t;
}
double distance_to_line(point p, point a, point b) {
vector v1 = b - a, v2 = p - a;
return fabs(cross(v1, v2)) / length(v1);
}
double distance_to_line(point p, line L) {
vector v2 = p - L.p;
return fabs(cross(L.p, v2)) / length(L.p);
}
double polygon_area(polygon &poly) {
double ans = 0;
for (int i = 1, n = poly.size(); i < n - 1; i++)
ans += cross(poly[i] - poly[0], poly[i+1] - poly[0]);
return ans / 2;
}
polygon convex_hull(polygon &p) {
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int m = 0, n = p.size(); polygon ch(n + 1);
for (int i = 0; i < n; i++) {
while (m > 1 && cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
for (int i = n - 2, k = m; i >= 0; i--) {
while (m > k && cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
ch[m++] = p[i];
}
if (n > 1) m--; ch.resize(m);
return ch;
}
polygon half_plane_intersection(line_set &L) {
sort(L.begin(), L.end());
int first, last, n = L.size();
point *p = new point[n]; line *q = new line[n];
q[first=last=0] = L[0];
for (int i = 1; i < n; i++) {
while (first < last && !on_left(L[i], p[last-1])) last--;
while (first < last && !on_left(L[i], p[first])) first++;
q[++last] = L[i];
if (fabs(cross(q[last].v, q[last-1].v)) < eps)
if (on_left(q[--last], L[i].p)) q[last] = L[i];
if (first < last) p[last-1] = line_intersection(q[last-1], q[last]);
}
polygon ans;
while (first < last && !on_left(q[first], p[last-1])) last--;
if (last - first <= 1) return ans;
p[last] = line_intersection(q[last], q[first]);
for (int i = first; i <= last; i++) ans.push_back(p[i]);
return ans;
}
}
using namespace std;
using namespace geometry;
int n;
double ans;
polygon p;
inline void chkmx(int u, int v, int &a, int &b) {
while ((a + 1) % n != v && distance_to_line(p[a+1], p[u], p[v]) > distance_to_line(p[a], p[u], p[v]))
a = (a + 1) % n;
while ((b + 1) % n != u && distance_to_line(p[b+1], p[u], p[v]) > distance_to_line(p[b], p[u], p[v]))
b = (b + 1) % n;
ans = max(ans,
length(p[u] - p[v]) * (distance_to_line(p[b], p[u], p[v]) + distance_to_line(p[a], p[u], p[v])));
}
int main() {
double x, y;
cin >> n; p.resize(n);
for (int i = 0; i < n; i++)
cin >> x >> y, p[i] = point(x, y);
p = convex_hull(p);
n = p.size();
for (int u = 0, v = 1, a = 0, b = 1; u < n; u++) {
while (1) {
int diff = dcmp(cross(p[(u+1)%n] - p[u], p[(v+1)%n] - p[v]));
if (diff <= 0) {
chkmx(u, v, a, b);
if (diff == 0) chkmx(u, (v + 1) % n, a, b);
break;
}
if (b == v) b = (b + 1) % n;
v = (v + 1) % n;
}
if (a == u) a = (a + 1) % n;
}
printf("%.3lf\n", ans / 2);
}