POJ3301的三分算法如何应用于求解最小覆盖正方形问题？

本文共计447个文字，预计阅读时间需要2分钟。

题目：给定n个点，找出一个最小的正方形去覆盖所有点。思路：如果题目中规定正方形必须包含x轴和y轴，那么可以通过以下步骤解决问题：

1.给定n个点，首先计算所有点的x坐标和y坐标的最大值和最小值。

2.根据最大值和最小值，确定正方形的边长为(max_x - min_x) + (max_y - min_y)。

3.正方形的位置可以放在所有点的中心，即x坐标为(min_x + max_x) / 2，y坐标为(min_y + max_y) / 2。

4.输出正方形的四个顶点坐标。

题意给你n个点让你找一个最小的正方形去覆盖所有点。思路想一下如果题目中规定正方形必须和x轴平行那么我 题意       给你n个点让你找一个最小的正方形去覆盖所有点。 思路

      想一下如果题目中规定正方形必须和x轴平行那么我们是不是直接找到最大的x差和最大的y差取最大就行了但是这个题目没说平行那么我们就旋转这个正方形因为是凸性或者凹性用三分去枚举正方形的角度[0,PI/2],然后缩小范围知道找到答案。公式是

nowx x * cos(du) - y * sin(d)    nowy x * sin(du)   y *cos(d)

#include#include#define N 50#define eps 0.000001double PI acos(-1.0);typedef struct{double x ,y;}NODE;NODE node[N];double maxx(double x ,double y){return x > y ? x : y;}double minn(double x ,double y){return x < y ? x : y;}double abss(double x){return x < 0 ? -x : x;}double now(double phi ,int n){double Max_x -100000000 ,Min_x 100000000;double Max_y -100000000 ,Min_y 100000000;for(int i 1 ;i < n ;i ){double xx node[i].x * cos(phi) - node[i].y * sin(phi);double yy node[i].x * sin(phi) node[i].y * cos(phi);Max_x maxx(xx ,Max_x);Max_y maxx(yy ,Max_y);Min_x minn(Min_x ,xx);Min_y minn(Min_y ,yy);}return maxx((Max_x - Min_x) ,(Max_y - Min_y));}int main (){int t ,n ,i;double low ,mid ,mmid ,up ,ans;scanf("%d" ,while(t--){scanf("%d" ,for(i 1 ;i < n ;i )scanf("%lf %lf" ,low 0 ,up PI / 2.0;while(1){mid (low up) / 2.0;mmid (mid up) / 2.0;double dis1 now(mid ,n);double dis2 now(mmid ,n);if(dis1 < dis2) up mmid;else low mid;if(abss(dis1 - dis2) < eps)break;ans minn(dis1 ,dis2);}printf("%.2lf\n" ,ans * ans);}return 0;}