题意：求能将所有点覆盖的最小体积的圆锥。
体积变化为凹形，故可以三分半径r，再枚举各个点找最大的高h。
View Code
1 /* 2 Author:Zhaofa Fang 3 Lang:C++ 4 */ 5 #include <cstdio> 6 #include <cstdlib> 7 #include <sstream> 8 #include <iostream> 9 #include <cmath> 10 #include <cstring> 11 #include <algorithm> 12 #include <string> 13 #include <utility> 14 #include <vector> 15 #include <queue> 16 #include <stack> 17 #include <map> 18 #include <set> 19 using namespace std; 20 21 typedef long long ll; 22 #define DEBUG(x) cout<< #x << ':' << x << endl 23 #define REP(i,n) for(int i=0;i < (n);i++) 24 #define REPD(i,n) for(int i=(n-1);i >= 0;i--) 25 #define FOR(i,s,t) for(int i = (s);i <= (t);i++) 26 #define FORD(i,s,t) for(int i = (s);i >= (t);i--) 27 #define PII pair<int,int> 28 #define PB push_back 29 #define MP make_pair 30 #define ft first 31 #define sd second 32 #define lowbit(x) (x&(-x)) 33 #define INF (1<<30) 34 35 36 const double PI = 3.1415926; 37 int n; 38 struct point 39 { 40 double x,y,z; 41 }P[10005]; 42 double volume(double r,double h) 43 { 44 return PI*r*r*h/3.0; 45 } 46 47 double fun(double r,double &hx) 48 { 49 double MAX = 0; 50 REP(i,n) 51 { 52 double h = P[i].z*r/(r-sqrt(P[i].x*P[i].x+P[i].y*P[i].y)); 53 MAX = max(MAX,h); 54 } 55 hx = MAX; 56 return volume(r,MAX); 57 } 58 int main() 59 { 60 //freopen("in","r",stdin); 61 //freopen("out","w",stdout); 62 int T; 63 scanf("%d",&T); 64 while(T--) 65 { 66 scanf("%d",&n); 67 double M=0; 68 REP(i,n) 69 { 70 scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].z); 71 M = max(M,sqrt(P[i].x*P[i].x+P[i].y*P[i].y)); 72 } 73 double l=M+1e-6,r=100000.0,hx; 74 while(fabs(l-r) > 1e-6) 75 { 76 double lm = l + (r-l)/3.0; 77 double rm = r - (r-l)/3.0; 78 if(fun(lm,hx)<fun(rm,hx))r = rm; 79 else l = lm; 80 } 81 printf("%.3f %.3f\n",hx,r); 82 } 83 return 0; 84 }