POJ 3301 三分（最小覆盖正方形）

题意：
      给你n个点，让你找一个最小的正方形去覆盖所有点。
思路：

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

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

#include<stdio.h> #include<math.h>#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" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node[i].x ,&node[i].y);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; }

总结

以上是生活随笔为你收集整理的POJ 3301 三分（最小覆盖正方形）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。