题目大意:给出平面上的一些点,问面积最小的矩形满足覆盖所有的点。
思路:覆盖问题和不是凸包上的点没关系,先做凸包。根据贪心的思想,这个覆盖了所有点的矩形肯定至少有一条边与凸包上的边重合,那么我们枚举凸包上的每一条边,对于这个已经确定了一条边的矩形,不难确定其他三个边。注意到已知当前直线的向量,就可以求出两侧和对面的向量,而这三个向量随着枚举的边的移动是单调的,所以就可以用旋转卡壳来卡住剩下的三条边。
但是旋转卡壳时的初值会出问题,如果按照逆时针的顺序求出剩下的三条边的时候,要想通过向量直接卡第三条边的方向是不行的,因为它和第一条边正好是反过来的,所以对于同一条边来说,与第一条边的夹角和第三条边的夹角一个是顺时针另一个是逆时针。这肯定会出问题。所以要预处理出枚举的第一条边,算出三个边的位置,作为旋转卡壳的初值。可以证明,在凸包上的其他边每次旋转肯定不会超过180°,所以不会发生类似的bug。
CODE:
#define _CRT_SECURE_NO_WARNINGS #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define MAX 50010 using namespace std; struct Point{ double x,y; Point(double _,double __):x(_),y(__) {} Point() {} Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator *(double a)const { return Point(x * a,y * a); } bool operator <(const Point &a)const { return x == a.x ? y < a.y:x < a.x; } void Read() { scanf("%lf%lf",&x,&y); } }point[MAX],stack[MAX],ans[5]; int top; inline double Calc(const Point &p1,const Point &p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } inline double Cross(const Point &p1,const Point &p2) { return p1.x * p2.y - p1.y * p2.x; } struct Line{ Point p,v; Line(Point _,Point __):p(_),v(__) {} Line() {} }; int points; inline bool cmp(const Point &p1,const Point &p2) { return p1.y > p2.y; } inline void Add(const Point &p,int bottom) { while(top > bottom && Cross(p - stack[top - 1],stack[top] - stack[top - 1]) >= 0) --top; stack[++top] = p; } inline Point GetIntersection(const Line &l1,const Line &l2) { Point u = l1.p - l2.p; double t = Cross(l2.v,u) / Cross(l1.v,l2.v); return l1.p + l1.v * t; } double min_area = 1e15; inline void GetArea(const Point &p1,const Point &p2,const Point &p3,const Point &p4,const Point &v1,const Point &v2,const Point &v3,const Point &v4) { Line l1(p1,v1),l2(p2,v2),l3(p3,v3),l4(p4,v4); Point t1 = GetIntersection(l1,l2); Point t2 = GetIntersection(l2,l3); Point t3 = GetIntersection(l3,l4); Point t4 = GetIntersection(l4,l1); if(Cross(t2 - t1,t4 - t1) < min_area) { min_area = Cross(t2 - t1,t4 - t1); ans[1] = t1,ans[2] = t2,ans[3] = t3,ans[4] = t4; } } void RotatingCalipers() { int p1 = 1; Point now = stack[2] - stack[1]; Point r(-now.y,now.x),u(-now.x,-now.y),l(now.y,-now.x); while(Cross(stack[p1 + 1] - stack[p1],r) > 0) p1 = (p1 + 1) % top; int p2 = p1; while(Cross(stack[p2 + 1] - stack[p2],u) > 0) p2 = (p2 + 1) % top; int p3 = p2; while(Cross(stack[p3 + 1] - stack[p3],l) > 0) p3 = (p3 + 1) % top; for(int i = 1; i < top; ++i) { now = stack[i + 1] - stack[i]; r = Point(-now.y,now.x),u = Point(-now.x,-now.y),l = Point(now.y,-now.x); while(Cross(stack[p1 + 1] - stack[p1],r) > 0) p1 = (p1 + 1) % top; while(Cross(stack[p2 + 1] - stack[p2],u) > 0) p2 = (p2 + 1) % top; while(Cross(stack[p3 + 1] - stack[p3],l) > 0) p3 = (p3 + 1) % top; GetArea(stack[i],stack[p1],stack[p2],stack[p3],now,r,u,l); } } int main() { cin >> points; for(int i = 1; i <= points; ++i) point[i].Read(); sort(point + 1,point + points + 1); int t = 1; while(point[t + 1].x == point[1].x) ++t; sort(point + 1,point + t + 1,cmp); stack[++top] = point[1]; for(int i = 2; i <= points; ++i) Add(point[i],1); int temp = top; for(int i = points - 1; i; --i) Add(point[i],temp); stack[0] = stack[--top]; RotatingCalipers(); cout << fixed << setprecision(5) << min_area << endl; int p = 1; for(int i = 2; i <= 4; ++i) if(ans[i].y < ans[p].y || (ans[i].y == ans[p].y && ans[i].x < ans[p].x)) p = i; for(int i = p; i <= 4; ++i) cout << fixed << setprecision(5) << ans[i].x << ' ' << ans[i].y << endl; for(int i = 1; i < p; ++i) cout << fixed << setprecision(5) << ans[i].x << ' ' << ans[i].y << endl; return 0; }
BZOJ 1185 HNOI 2007 最小矩形覆盖 旋转卡壳
原文:http://blog.csdn.net/jiangyuze831/article/details/43058667