|
楼主 |
发表于 2018-2-18 20:55:25
|
显示全部楼层
本题应用了三分算法,参考文章http://blog.csdn.net/littlewhite520/article/details/70144763
给出平面上一些点(坐标),让我们在平面上选择一个正方形能够覆盖这些所有的点,求这个正方形的最小面积。
我们很容易找到一个符合要求的正方形,也就是所有边都平行于坐标轴的正方形,那么我们就只找平行于坐标轴的正方形,我们将每个点都旋转一定的角度,他们的相对位置不变,而正方形却相对于点在旋转,面积在改变,那么就可以找到最小的正方形.
我们只需要考虑最优的旋转角度.
假设旋转的角度为f,初始点的坐标为(x,y)与x轴的夹角为a,距离坐标原点的长度为len,那么x = cos(a)*len,y = sin(a)*len,nx = cos(a+f)*len,ny = sin(a+f)*len
拆开nx = cos(a)*cos(f)*len-sin(a)*sin(f)*len,ny = sin(a)*cos(f)*len+cos(a)*sin(f)*len
也就是说 nx = cos(f)*x-sin(f)*y,ny = sin(f)*x+cos(f)*y;
正方形的边长等于max(rightx-leftx,upy-downy) = max(cos(f)*(x1-x2)-sin(f)*(y1-y2),sin(f)*(x1-x2)+cos(f)*(y1-y2))(x1>x2 && y1>y2)
等于 max(sqrt((x1-x2)^2+(y1-y2)^2)sin(f+p1),sqrt((x1-x2)^2+(y1-y2)^2)sin(f+p2))
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #include<cmath>
- #define maxn 31
- #define pi acos(-1.0)
- #define eps 1e-12
- #define inf 0xfffffff
- using namespace std;
- struct E
- {
- double x,y;
- E toa(double a)
- {
- E ans;
- ans.x=x*cos(a)-y*sin(a);
- ans.y=x*sin(a)+y*cos(a);
- return ans;
- }
-
- }a[maxn];
- int T,n;
- double cal(double x)
- {
- double minx=inf,miny=inf;
- double maxx=-inf,maxy=-inf;
- for(int i=1;i<=n;i++)
- {
- E ans;
- ans=a[i].toa(x);
- minx=min(minx,ans.x),miny = min(miny,ans.y);
- maxx = max(maxx,ans.x),maxy = max(maxy,ans.y);
- }
- return max(maxx-minx,maxy-miny);
- }
- int main()
- {
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%lf%lf",&a[i].x,&a[i].y);
- double l=0,r=pi,mid,mmid;
- while(l+eps<r)
- {
- mid=(l+r)/2;
- mmid=(mid+r)/2;
- if(cal(mid)>cal(mmid))
- l=mid;
- else
- r=mmid;
- }
- double len=cal(l);
- printf("%.2lf\n",len*len);
- }
- return 0;
- }
复制代码 |
|