題意:
? ? ? 讓你找到一個最小的圓柱去覆蓋所有的豎直的線段..
思路:
? ? ? 三分,直接去三分他的半徑,因為想下,如果某個半徑是最優值,那么

從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 三分求最小圆锥的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。