[HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 2081  Solved: 920
[Submit][Status][Discuss]

Description

给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,
输出所求矩形的面积和四个顶点坐标
 

Input

第一行为一个整数n(3<=n<=50000)
从第2至第n+1行每行有两个浮点数,表示一个顶点的x和y坐标,不用科学计数法
 

Output

第一行为一个浮点数,表示所求矩形的面积(精确到小数点后5位),
接下来4行每行表示一个顶点坐标,要求第一行为y坐标最小的顶点,
其后按逆时针输出顶点坐标.如果用相同y坐标,先输出最小x坐标的顶点

Sample Input

6 1.0 3.00000
1 4.00000
2.0000 1
3 0.0000
3.00000 6
6.0 3.0

Sample Output

18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000

HINT

 

Source

[Submit][Status][Discuss]

HOME Back

首先有一个结论,矩形的一条边一定在凸包上!!!
枚举凸包上的边
用旋转卡壳在凸包上找矩形另外三点。。
差不多吧,其它三个点可以找的吧,而且也是有单调性的。
 #pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio> #define eps 0.00000001
#define N 50007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,tot;
double ans=1e60;
struct P
{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
friend bool operator<(P a,P b){return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;}
friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
friend bool operator!=(P a,P b){return !(a==b);}
friend P operator+(P a,P b){return P(a.x+b.x,a.y+b.y);}
friend P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
friend double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
friend P operator*(P a,double b){return P(a.x*b,a.y*b);}
friend double operator/(P a,P b){return a.x*b.x+a.y*b.y;}
friend double dis(P a){return sqrt(a.x*a.x+a.y*a.y);}
}p[N],q[N],t[]; bool cmp(P a,P b)
{
double t=(a-p[])*(b-p[]);
if(fabs(t)<eps)return dis(p[]-a)-dis(p[]-b)<;
return t>;
}
void Graham()
{
for (int i=;i<=n;i++)
if(p[i]<p[])swap(p[i],p[]);
sort(p+,p+n+,cmp);
q[++tot]=p[];
for (int i=;i<=n;i++)
{
while(tot>&&(q[tot]-q[tot-])*(p[i]-q[tot])<eps)tot--;
q[++tot]=p[i];
}
q[]=q[tot];//凸包是一个回路。
}
void RC()
{
int l=,r=,p=;
double L,R,D,H;
for (int i=;i<tot;i++)
{
D=dis(q[i]-q[i+]);
while((q[i+]-q[i])*(q[p+]-q[i])-(q[i+]-q[i])*(q[p]-q[i])>-eps)p=(p+)%tot;
while((q[i+]-q[i])/(q[r+]-q[i])-(q[i+]-q[i])/(q[r]-q[i])>-eps)r=(r+)%tot;
if(i==)l=r;
while((q[i+]-q[i])/(q[l+]-q[i])-(q[i+]-q[i])/(q[l]-q[i])<eps)l=(l+)%tot;
L=(q[i+]-q[i])/(q[l]-q[i])/D,R=(q[i+]-q[i])/(q[r]-q[i])/D;
H=(q[i+]-q[i])*(q[p]-q[i])/D;
if(H<)H=-H;
double tmp=(R-L)*H;
if(tmp<ans)
{
ans=tmp;
t[]=q[i]+(q[i+]-q[i])*(R/D);
t[]=t[]+(q[r]-t[])*(H/dis(t[]-q[r]));
t[]=t[]-(t[]-q[i])*((R-L)/dis(q[i]-t[]));
t[]=t[]-(t[]-t[]);
}
}
}
int main()
{
n=read();
for (int i=;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
Graham();
RC();
printf("%.5lf\n",ans);
int fir=;
for (int i=;i<=;i++)
if(t[i]<t[fir])fir=i;
for (int i=;i<=;i++)
printf("%.5lf %.5lf\n",t[(i+fir)%].x,t[(i+fir)%].y);
}

最新文章

  1. nodejs利用ajax实现网页无刷新上传图片
  2. Wireshark找不到网络接口问题
  3. 旅游风景展示应用源码iPad版
  4. Think PHP 提示验证码输入错误
  5. Swipecards
  6. EC读书笔记系列之19:条款49、50、51、52
  7. AS3 Post 参数和ByteArray的方法及服务器端接收
  8. VS2010程序打包操作
  9. Java语言国际化
  10. WPF中带水印的Textbox
  11. Linux网络编程客户\服务器设计范式
  12. Spring中整合Cage,实现验证码功能
  13. Java-Io之文件File
  14. 原生javascript写自己的运动库(匀速运动篇)
  15. MYSQL配置主从同步
  16. sql学习书籍
  17. 把JavaScript对象转化成JSON对象
  18. 3790:最短路径问题(HDU)
  19. Stackoverflow 珠玑:用于分组的 LINQ 扩展方法
  20. python第三十七天--异常--socket

热门文章

  1. vue数据绑定html
  2. Windows下如何安装composer
  3. PHP处理mysql事务
  4. const用法总结(通俗易懂)
  5. Windows手工创建服务方法
  6. Codeforces Round #428 (Div. 2) C. dfs
  7. MyBatis---简单关系查询
  8. border与透明边框
  9. android版本vqmon移植IOS版
  10. Maven学习 (二) Eclipse 上安装 Maven3插件