当前位置 : 主页 > 网络编程 > 其它编程 >

POJ3301三分(最小覆盖正方形)

来源:互联网 收集:自由互联 发布时间:2023-07-02
题意给你n个点让你找一个最小的正方形去覆盖所有点。思路想一下如果题目中规定正方形必须和x轴平行那么我 题意       给你n个点让你找一个最小的正方形去覆盖所有点。 思路    
题意给你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;}

上一篇:乐优商城(十二)购物车
下一篇:没有了
网友评论