注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1185][HNOI2007]最小矩形覆盖  

2015-02-26 21:20:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1185: [HNOI2007]最小矩形覆盖

MLGB我从下午起床开始对着网上错的程序调到现在……
而且我害怕标程出错还特意从两个地方找了程序,
结果两个非常有默契地输出结果一样,其中一个的方案还是平行四边形……
感动得我都开始怀疑人生了[BZOJ1185][HNOI2007]最小矩形覆盖 - 时光机 - 时光机TimeMachine
俺的数据……
INPUT:
4
0.00004 -9.99989
0.00006 -9.99984
-9.99995 4.00035
5.00008 8.99989
OUTPUT:
259.99937
-4.80036 -11.59987
10.19967 -6.60033
5.00008 8.99989
-9.99995 4.00035
但是据说官方数据答案全是整数……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 5E4+100;
const double eps = 1e-10;
int scan(){int i=0;scanf("%d",&i);return i;}
int n,m,ke[2][N],list[N],top,ed[4];
int DEBUG;
double ans[5],xl[2][N];
struct Point{Point (double a=0,double b=0){x=a;y=b;}double x,y;
void print(){printf("%.5f %.5f\n",x,y);}}data[N],ap[4],tp[4];
bool cmp(int A,int B){
Point &a=data[A],&b=data[B];
if(fabs(a.x-b.x)<=eps)return a.y<b.y;
return a.x<b.x;
}
deque<int>dui;
Point operator + (const Point&a,const Point&b){return Point(a.x+b.x, a.y+b.y);}
Point operator - (const Point&a,const Point&b){return Point(a.x-b.x, a.y-b.y);}
Point operator * (const Point&a,double b){return Point(a.x*b, a.y*b);}
Point operator / (const Point&a,double b){return Point(a.x/b, a.y/b);}
bool operator < (const Point&a,const Point&b){
if(fabs(a.y-b.y)>eps)return a.y<b.y;
return a.x<b.x;
}
double Dot(const Point &a,const Point &b){return a.x*b.x+a.y*b.y;}
double Cross(const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
double Length(const Point&a){return sqrt(Dot(a,a));}
//pay attention a.x==b.x
double calck(const Point &a,const Point &b){return (b.y-a.y)/(b.x-a.x);}
bool better(const Point&a,const Point&b,const Point&c,short t){
if(!t)return Cross(a-b,b-c)>=0;
else return Cross(a-b,b-c)<=0;
}
Point rotate(const Point&a){return Point(a.y,-a.x);}
void update(double k){
Point v=Point(1,k),tv;
if(data[ed[0]].x>data[ed[2]].x){
swap(ed[0],ed[2]),swap(ed[1],ed[3]);
v=rotate(v)*-1;
}
swap(ed[1],ed[2]);
for(int i=0;i<4;i++){
tv = data[ed[(i+1)&3]]-data[ed[i]];
double len=Dot(tv,v)/Length(v);
tv=v/Length(v)*len;

tp[i]=data[ed[i]]+tv;
v=rotate(v);
}
ans[1]=fabs(Cross(tp[2]-tp[1],tp[0]-tp[1]));
//printf("[%.5f]\n",ans[1]);
if(ans[1]<ans[0]){
ans[0]=ans[1];
for(int i=0;i<4;i++)ap[i]=tp[i];
}

}
bool dcmp0(double a,double b){
if(fabs(a-b)<eps)return 1>1;
return a>b;
}
bool dcmp1(double a,double b){
if(fabs(a-b)<eps)return 1<1;
return a<b;
}
int main(){
freopen("in.txt","r",stdin);
int i,j;double a,b;
n = scan();
//特别check一下平行坐标轴的
ans[1]=ans[3]=1e10;ans[2]=ans[4]=-1e10;
for(i=1;i<=n;i++){
scanf("%lf%lf",&a,&b);
data[i]=Point(a,b);
ans[1]=min(ans[1],a);ans[3]=min(ans[3],b);
ans[2]=max(ans[2],a);ans[4]=max(ans[4],b);
list[i]=i;
}
//start
ans[0]=(ans[2]-ans[1])*(ans[4]-ans[3]);
ap[0]=Point(ans[1],ans[3]);ap[1]=Point(ans[1],ans[4]);
ap[2]=Point(ans[2],ans[4]);ap[3]=Point(ans[2],ans[3]);
//printf("<%.5f>\n",ans[0]);
//
sort(list+1,list+1+n,cmp);
for(i=1;i<=n;i++)
if(i==n||fabs(data[list[i]].x-data[list[i+1]].x)>eps){
while((j=dui.size())>1&&better(data[dui[j-2]],data[dui[j-1]],data[list[i]],0))dui.pop_back(),top--;
if(dui.empty())xl[0][++top]=1e50;
else xl[0][++top]=calck(data[dui.back()],data[list[i]]);
dui.push_back(list[i]);ke[0][top]=list[i];
}
ke[0][0]=top;top=0;
dui.clear();
for(i=1;i<=n;i++)
if(i==1||fabs(data[list[i]].x-data[list[i-1]].x)>eps){
while((j=dui.size())>1&&better(data[dui[j-2]],data[dui[j-1]],data[list[i]],1))dui.pop_back(),top--;
if(dui.empty())xl[1][++top]=-1e50;
else xl[1][++top]=calck(data[dui.back()],data[list[i]]);
dui.push_back(list[i]);ke[1][top]=list[i];
}
ke[1][0]=top;

list[0]=0;
//注意之后就不要处理k=0的情况了
//up
for(i=1;i<ke[0][0];i++){
double nowk = xl[0][i+1],ek;
if(fabs(nowk)<=eps)continue;ek=-1/nowk;
ed[0]=i;
ed[1]=lower_bound(xl[1]+1,xl[1]+1+ke[1][0],nowk,dcmp1)-xl[1]-1;
ed[2]=lower_bound(xl[0]+1,xl[0]+1+ke[0][0],ek,dcmp0)-xl[0]-1;
ed[3]=lower_bound(xl[1]+1,xl[1]+1+ke[1][0],ek,dcmp1)-xl[1]-1;
for(j=0;j<4;j++)ed[j]=ke[j&1][ed[j]];
update(nowk);
}
//down
for(i=1;i<ke[1][0];i++){
double nowk = xl[1][i+1],ek;
if(fabs(nowk)<=eps)continue;ek=-1/nowk;
ed[0]=lower_bound(xl[0]+1,xl[0]+1+ke[0][0],nowk,dcmp0)-xl[0]-1;
ed[1]=i;
ed[2]=lower_bound(xl[0]+1,xl[0]+1+ke[0][0],ek,dcmp0)-xl[0]-1;
ed[3]=lower_bound(xl[1]+1,xl[1]+1+ke[1][0],ek,dcmp1)-xl[1]-1;

for(j=0;j<4;j++)ed[j]=ke[j&1][ed[j]];
update(nowk);
}
//output ans
printf("%.5f\n",ans[0]);
j=0;
for(i=1;i<4;i++)
if(ap[i]<ap[j])j=i;
for(i=0;i<4;i++)ap[(j-i+4)&3].print();
return 0;
}

题解:
计算几何:凸包
枚举凸包上的某个边作为矩形的一边……然后通过二分/三分/单调性 得到其它卡着的矩形位置就做完了……
需要注意的地方:
如果是二分斜率要特判平行坐标轴的情况
  评论这张
 
阅读(713)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017