hdu3756 三分求最小圆锥
最小 三分
2023-09-11 14:14:00 时间
题意:
让你找到一个最小的圆柱去覆盖所有的竖直的线段..
思路:
三分,直接去三分他的半径,因为想下,如果某个半径是最优值,那么
让你找到一个最小的圆柱去覆盖所有的竖直的线段..
思路:
三分,直接去三分他的半径,因为想下,如果某个半径是最优值,那么
从R(MAX->now->MIN)是的 V肯定是先增大然后减小再增大,也就是满足凹凸性,所以可以三分,三分的时候根据当前的半径我们可以枚举每一个点,通过相似三角形去找到最大的H作为当前的H,然后根据V三分搜索就行了,对于low的初始值我赋的是 x_y平面上离原点距离最远的那个的距离+ 1e-9 ,防止被除数是0的情况.其他的没啥就是简单的三分,如果你想卡排名就不断缩小eps知道wa为止.
#include<stdio.h> #include<math.h> #define eps 1e-9 #define N 10000 + 100 double PI = acos(-1.0); typedef struct { double x ,y ,z; }NODE; NODE node[N]; double Q_H(double R ,int n) { double MAX = 0; for(int i = 1 ;i <= n ;i ++) { double tmp = sqrt(node[i].x * node[i].x + node[i].y * node[i].y); double now = R / (R - tmp) * node[i].z; if(MAX < now) MAX = now; } return MAX; } double Q_V(double R ,double H ,int n) { return PI * R * R / 3 * H; } void solve(int n ,double loww) { double low ,up ,mid ,mmid; low = loww ,up = 1000000000; double v1 ,v2 ,h1 ,h2; while(1) { mid = (low + up) / 2; mmid = (mid + up) / 2; h1 = Q_H(mid ,n); h2 = Q_H(mmid ,n); v1 = Q_V(mid ,h1 ,n); v2 = Q_V(mmid ,h2 ,n); if(v1 > v2) low = mid; else up = mmid; if(up - low < eps) break; } printf("%.4lf %.4lf\n" ,h1 ,mid); return ; } int main () { int t ,n ,i; scanf("%d" ,&t); while(t--) { scanf("%d" ,&n); double ma = 0; for(i = 1 ;i <= n ;i ++) { scanf("%lf %lf %lf" ,&node[i].x ,&node[i].y ,&node[i].z); double now = sqrt(node[i].x * node[i].x + node[i].y * node[i].y); if(ma < now) ma = now; } solve(n ,ma + eps); } return 0; }
相关文章
- hdu3756 三分求最小圆锥
- hdu3870 基于最短路的最小割
- 【网络流24题】最小路径覆盖问题(最大流)
- 把数组排成最小的数
- LeetCode高频题:从矩阵matrix的左上角,只能往右往下走,走到右下角的最小路径和是多少
- 求二叉树的最小高度
- 最小错误率贝叶斯决策
- 【HDU 4408】Minimum Spanning Tree(最小生成树计数)
- 【蓝桥杯Java组】数论基础—素数筛、最大公约数、最小公倍数
- [LeetCode] 910. Smallest Range II 最小区间之二
- 最小二乘法求回归直线方程的推导过程
- 【bzoj1976】[BeiJing2010组队]能量魔方 Cube 网络流最小割
- 【bzoj1266】[AHOI2006]上学路线route 最短路+最小割