POJ 3301 三分(最小覆盖正方形)
最小 poj 覆盖 正方形 三分
2023-09-11 14:13:59 时间
题意:
给你n个点,让你找一个最小的正方形去覆盖所有点。
思路:
给你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.000001
double 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 三分(最小覆盖正方形)
- POJ 1716 区间最小点个数
- 【CJOJ2484】【Luogu2805】最小函数值(函数最小值)
- 【华为OD机试真题 python】等和子数组最小和【2022 Q4 | 100分】
- POJ 1258 Agri-Net (最小生成树+Prim)
- BZOJ4537 : [Hnoi2016]最小公倍数
- hihoCoder #1127 : 二分图二·二分图最小点覆盖和最大独立集
- 最小生成树-Kruskal算法模板
- HDU 6779 Drink (最小费用流)
- POJ 3686 The Windy's (最小费用流或最佳完全匹配)
- POJ 3723 Conscription (最小生成树)
- 剑指 Offer 11. 旋转数组的最小数字
- Constructing Roads POJ - 2421 (最小生成树)
- 最小二乘法 及 梯度下降法 运行结果对比(Python版)
- 【POJ 1789】Truck History(最小生成树)
- 【POJ 2485】Highways(Prim最小生成树)
- (JAVA编程练习):输入两个正整数m和n,求其最大公约数和最小公倍数。
- 最小码距和检错纠错能力的关系
- poj 3026 Borg Maze bfs+最小生成树
- 【bzoj2238】Mst 最小生成树+树链剖分+线段树
- 【bzoj2007】[Noi2010]海拔 最小割+对偶图+最短路
- A - 还是畅通工程(最小生成树)