题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1185
题意:
给出二维平面上的 n 个点, 问你将所有点覆盖的最小矩形面积.
题解:
先找出凸包, 然后旋转卡壳.
在旋转卡壳中有一个结论: 最小覆盖矩形一定有一条边在凸包上.
所以先枚举矩形在凸包上的那条边 (p[i],p[i+1]), 然后利用单调性找出 p[i] 的对踵点 p[u].
至于左右两侧的切点 p[l] 和 p[r], 要利用它们连线在直线 (p[i],p[i+1]) 上投影长度的单调性求出.
最后将找出的矩形顶点再做一遍极角排序即可.
- AC Code:
- #include <iostream>
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #include <algorithm>
- #define MAX_N 50005
- #define INF_LF 1e14
- #define EPS 1e-7
- using namespace std;
- struct Coor
- {
- double x,y;
- Coor(double _x,double _y) { x=_x,y=_y; }
- Coor(){}
- friend Coor operator + (const Coor &a,const Coor &b)
- {
- return Coor(a.x+b.x,a.y+b.y);
- }
- friend Coor operator - (const Coor &a,const Coor &b)
- {
- return Coor(a.x-b.x,a.y-b.y);
- }
- friend Coor operator * (const Coor &a,double b)
- {
- return Coor(a.x*b,a.y*b);
- }
- friend Coor operator / (const Coor &a,double b)
- {
- return Coor(a.x/b,a.y/b);
- }
- friend double len(const Coor &a,const Coor &b)
- {
- return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
- }
- friend double dot(const Coor &a,const Coor &b)
- {
- return a.x*b.x+a.y*b.y;
- }
- friend double cross(const Coor &a,const Coor &b)
- {
- return a.x*b.y-a.y*b.x;
- }
- friend double area(const Coor &a,const Coor &b,const Coor &c)
- {
- return fabs(cross(b-a,c-a));
- }
- friend double length(const Coor &a)
- {
- return sqrt(dot(a,a));
- }
- friend double pro(const Coor &a,const Coor &b)
- {
- return dot(a,b)/length(b);
- }
- friend Coor proc(const Coor &a,const Coor &b,const Coor &c)
- {
- Coor v=c-b;
- return b+v*dot(v,a-b)/dot(v,v);
- }
- };
- int n,tot=0;
- double ans=INF_LF;
- Coor p[MAX_N];
- Coor con[MAX_N];
- Coor rect[MAX_N];
- void read()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
- }
- bool cmp(const Coor &a,const Coor &b)
- {
- double c=cross(a-p[1],b-p[1]);
- return c!=0 ? c>0 : len(p[1],a)<len(p[1],b);
- }
- inline bool eq(double x,double y)
- {
- return fabs(x-y)<EPS;
- }
- void graham()
- {
- for(int i=2;i<=n;i++)
- {
- if(p[i].y<p[1].y || (p[i].y==p[1].y && p[i].x<p[1].x))
- {
- swap(p[i],p[1]);
- }
- }
- sort(p+2,p+1+n,cmp);
- con[++tot]=p[1],con[++tot]=p[2];
- for(int i=3;i<=n;i++)
- {
- while(tot>=2 && cross(con[tot]-con[tot-1],p[i]-con[tot])<=0) tot--;
- con[++tot]=p[i];
- }
- }
- inline int mod(int x)
- {
- return ((x-1)%tot+tot)%tot+1;
- }
- void rc()
- {
- int u=2,l=1,r=1;
- for(int i=2;i<=tot;i++)
- {
- if(con[i].x<con[l].x || (con[i].x==con[l].x && con[i].y>con[l].y)) l=i;
- if(con[i].x>con[r].x || (con[i].x==con[r].x && con[i].y<con[r].y)) r=i;
- }
- for(int i=1;i<=tot;i++)
- {
- while(area(con[i],con[mod(i+1)],con[u])<area(con[i],con[mod(i+1)],con[mod(u+1)])) u=mod(u+1);
- while(pro(con[r]-con[l],con[mod(i+1)]-con[i])<pro(con[r]-con[mod(l+1)],con[mod(i+1)]-con[i])) l=mod(l+1);
- while(pro(con[r]-con[l],con[mod(i+1)]-con[i])<pro(con[mod(r+1)]-con[l],con[mod(i+1)]-con[i])) r=mod(r+1);
- double w=pro(con[r]-con[l],con[mod(i+1)]-con[i]);
- double h=area(con[i],con[mod(i+1)],con[u])/length(con[mod(i+1)]-con[i]);
- if(w*h<ans)
- {
- ans=w*h;
- Coor v=con[mod(i+1)]-con[i];
- rect[0]=proc(con[l],con[i],con[mod(i+1)]);
- rect[1]=proc(con[r],con[i],con[mod(i+1)]);
- rect[2]=proc(con[l],con[u],con[u]+v);
- rect[3]=proc(con[r],con[u],con[u]+v);
- }
- }
- for(int i=1;i<4;i++)
- {
- if(rect[i].y<rect[0].y || (rect[i].y==rect[0].y && rect[i].x<rect[0].x))
- {
- swap(rect[0],rect[i]);
- }
- }
- sort(rect+1,rect+4,cmp);
- for(int i=0;i<4;i++)
- {
- if(eq(rect[i].x,0)) rect[i].x=0;
- if(eq(rect[i].y,0)) rect[i].y=0;
- }
- }
- void work()
- {
- graham();
- rc();
- printf("%.5f\n",ans);
- for(int i=0;i<4;i++) printf("%.5f %.5f\n",rect[i].x,rect[i].y);
- }
- int main()
- {
- read();
- work();
- }
来源: http://www.bubuko.com/infodetail-2579519.html