題意:空間內有n個點,求一個最小體積的圓錐把所有點包進去。輸出圓錐的高和底面半徑。圓錐的底面圓心在(0,0),所有點的z坐標都大於等於0。
題解:因為圓錐體積是 V = 1/3 * π * r^2 * h ,這是一個二次函數,也就是個凸性函數,可以用三分查找的方式枚舉兩個高,然後找到對應的最小的r,比對兩個高得到的體積繼續三分查找。
#include
#include
#include
#include
using namespace std;
const double PI = acos(-1);
const double eps = 1e-9;
struct Point {
double x, y;
Point(double a = 0, double b = 0):x(a), y(b) {}
};
typedef Point Vector;
double dcmp(double x) {
if (fabs(x) < eps)
return 0;
return x < 0 ? -1 : 1;
}
Vector operator + (const Point& A, const Point& B) {
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (const Point& A, const Point& B) {
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (const Point& A, double a) {
return Vector(A.x * a, A.y * a);
}
Vector operator / (const Point& A, double a) {
return Vector(A.x / a, A.y / a);
}
double Cross(const Vector& A, const Vector& B) {
return A.x * B.y - A.y * B.x;
}
double Dot(const Vector& A, const Vector& B) {
return A.x * B.x + A.y * B.y;
}
double Length(const Vector& A) {
return sqrt(Dot(A, A));
}
bool operator < (const Point& A, const Point& B) {
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool operator == (const Point& A, const Point& B) {
return A.x == B.x && A.y == B.y;
}
const int N = 10005;
Point P[N], HP[N];
int n;
double solve(double h) {
double r = -1;
// (P[i].x - 0, P[i].y - h) (r - 0, 0 - h) 共線
for (int i = 0; i < n; i++)
if (P[i].x * h / (h - P[i].y) > r)
r = P[i].x * h / (h - P[i].y);
return r;
}
int main() {
while (scanf(%d, &n) == 1) {
double x, y, z, l = 0, r = 1e9;
for (int i = 0; i < n; i++) {
scanf(%lf%lf%lf, &x, &y, &z);
double d = sqrt(x * x + y * y);
P[i].x = d;
P[i].y = z;
l = max(l, z);
}
while (dcmp(r - l) > 0) {
double h1 = (l + r) / 2;
double h2 = (h1 + r) / 2;
double r1 = solve(h1);
double r2 = solve(h2);
if (r1 * r1 * h1 < r2 * r2 * h2)
r = h2;
else
l = h1;
}
printf(%.3lf %.3lf
, l, solve(l));
}
return 0;
}