题意:给你一些点,找出两个可以包含所有点的矩形,一个保证矩形面积最小,一个保证矩形周长最小,输出两个最小值

题解:首先根据所有点求一个凸包,再在这个凸包上枚举每条边,作为矩形的一条边(这样可以保证最小)

   接着根据旋转卡壳的思想求出另外三条边,这样枚举判断就好

   求另三条边时首先方向是确定了的,找点就是旋转卡壳,思想就是:枚举的任意两条边a与b,a的另三条边与b的另三条边都不会再a与b之间,并且b对应边一定最a对应边的        后面(注意是循环的边)那么就是说,我们可以使用类似双指针方式维护,但是时间复杂度却为O(n)

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const ll INF=1LL<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y) {};
inline Point operator-(const Point& a)const
{
return Point(x-a.x,y-a.y);
}
inline bool operator<(const Point& a)const
{
return sgn(x-a.x)<||zero(x-a.x)&&sgn(y-a.y)<;
}
inline Point operator+(const Point& a)const
{
return Point(x+a.x,y+a.y);
}
inline bool operator!=(const Point& a)const
{
return !(zero(x-a.x)&&zero(y-a.y));
}
};
typedef Point Vector;
struct Line
{
Point p;
Vector v;
double ang;//极角
Line() {};
Line(Point p,Vector v):p(p),v(v)
{
ang=atan2(v.y,v.x);
}
inline bool operator<(const Line& L)const
{
return ang<L.ang;
}
};
double Dis(Point A,Point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int ConvexHull(Point *p,int n,Point *convex)//求凸包
{
sort(p,p+n);
int m=;
for(int i=; i<n; ++i)
{
while(m>&&Cross(convex[m-]-convex[m-],p[i]-convex[m-])<)
{
m--;
}
convex[m++]=p[i];
}
int k=m;
for(int i=n-; i>=; --i)
{
while(m>&&Cross(convex[m-]-convex[m-],p[i]-convex[m-])<)
{
m--;
}
convex[m++]=p[i];
}
if(n>)
m--;
return m;
}
Point intersection(Point p1,Point p2,Point l1,Point l2)//交点坐标
{
Point ret=p1;//首先计算直线是否平行
double t=((p1.x-l1.x)*(l1.y-l2.y)-(p1.y-l1.y)*(l1.x-l2.x))
/((p1.x-p2.x)*(l1.y-l2.y)-(p1.y-p2.y)*(l1.x-l2.x));
ret.x+=(p2.x-p1.x)*t;
ret.y+=(p2.y-p1.y)*t;
return ret;//线段交点另外判断线段相交(同时判断是否平行)
}
Point now[Max],convex[Max];
double area,per;
double GetArea(Line up,Line down,Line left,Line right)//根据矩形四条线求面积
{
Point minx=intersection(left.p,left.p+left.v,down.p,down.p+down.v);
Point miny=intersection(right.p,right.p+right.v,down.p,down.p+down.v);
Point manx=intersection(left.p,left.p+left.v,up.p,up.p+up.v);
return Dis(minx,manx)*Dis(minx,miny);
}
double GetPer(Line up,Line down,Line left,Line right)
{
Point minx=intersection(left.p,left.p+left.v,down.p,down.p+down.v);
Point miny=intersection(right.p,right.p+right.v,down.p,down.p+down.v);
Point manx=intersection(left.p,left.p+left.v,up.p,up.p+up.v);
return (Dis(minx,manx)+Dis(minx,miny))*;
}
Vector Rotate(Vector A,double rad) //向量A逆时针旋转rad
{
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
void RotateStuck(int n)//旋转卡壳枚举矩形
{
for(int i=;i<n;++i)
{
convex[i+n]=convex[i];
convex[i+n+n]=convex[i];
}
area=per=Inf;
Line up,down,left,right;//四条直线
int i=,j=,k=,l=;//四条线的位置
for(; i<n; ++i)//枚举上这条线,则可以确定其他
{
up=Line(convex[i],convex[i+]-convex[i]);//其他三条直线所在的点与上这条线成单峰函数
k=max(i,k);//每次是逆时针旋转,保证是凸包上一条线或者后面的线
while(Cross(Rotate(up.v,Pi/),convex[k+]-convex[k])<)//通过旋转来判断
k++;
left=Line(convex[k],Rotate(up.v,Pi/));
j=max(k,j);
while(Cross(Rotate(up.v,Pi),convex[j+]-convex[j])<)
j++;
down=Line(convex[j],Rotate(up.v,Pi));
l=max(j,l);
while(Cross(Rotate(up.v,*Pi/),convex[l+]-convex[l])<)
l++;
right=Line(convex[l],Rotate(up.v,*Pi/));
area=min(area,GetArea(up,down,left,right));
per=min(per,GetPer(up,down,left,right));
}
return ;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
for(int i=; i<n; ++i)
{
scanf("%lf %lf",&now[i].x,&now[i].y);
}
int m= ConvexHull(now,n,convex);
RotateStuck(m);
printf("%.2f %.2f\n",area,per);
}
return ;
}

最新文章

  1. javascript面向对象系列第四篇——选项卡的实现
  2. Play Framework 完整实现一个APP(十)
  3. 2、软件设计师要阅读的书籍 - IT软件人员书籍系列文章
  4. Remove Duplicate Letters I &amp; II
  5. 2014百度之星资格赛 1001:Energy Conversion(水题,逻辑题)
  6. iOS多线程编程之Grand Central Dispatch(GCD)介绍和使用
  7. 用SQL语句添加删除修改字段
  8. Angular学习(2)- ng-app
  9. hdu 1195 Open the Lock
  10. Educational Codeforces Round 4 D. The Union of k-Segments 排序
  11. 20160409 javaweb 数据库连接池
  12. 关于PHP伪静态Rewrite设置
  13. PCRE的安装及使用
  14. Linq实现t-Sql的各种连接
  15. B - 瑶瑶带你玩激光坦克
  16. HttpURLConnection 411错误解决
  17. yii2修改默认控制器
  18. Chrome 的 PNaCl 还活着么?
  19. mariadb开启远程访问
  20. 困惑2----(已经OK)

热门文章

  1. 文件存储 FileUtil FileBaseDto
  2. 最详细的PHP flush()与ob
  3. Splay_Tree 模板(区间修改,旋转操作)
  4. 清空javascript数组数据
  5. javascript数组遍历for与for in区别详解
  6. 基础篇-java开发
  7. 转载的shell命令73条
  8. python并发编程&amp;多进程(二)
  9. Json模块的详细介绍(序列化)
  10. pip升级或卸载安装的包的方法