UVA1100

这道题的题解网络上很少。

我来传一波。

这道题第一个难点是如何量化稳定这个定义。

稳定，翻译成数学语言就是这个点的重心在底面的投影在底面内。

知道这个，此题可破。

然后就是考虑这个形状的可能性。题目条件限制很强，直接分类讨论就可以。把外边六个面分成三个部分讨论：面ABD,面ABE为第一组，面BCD,面BCE为第二组，面ACD,面ACE为第三组。然后就是对于每组来讲，可以有组内两个面共面，组内两个面在整个图形中是凸的，组内两个面在整个图形中是凹的三种情况。需要注意的是，最多只可能有一组是共面的，但是组内两个面在整个图形中是凹的这种情况的组数可以不止一个。想明白这个问题，对于每组的三种情况分别讨论即可。以下是代码君：草草写了一个，为了看起来方便。实际上可以把每组的情况写成一个函数，调用就行了，能省不少代码量。

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #include <vector> #include <sstream> #define eps 1e-8 #define pi acos(-1.0) using namespace std; struct point { double x, y, z; point(double x = 0, double y = 0, double z = 0) :x(x), y(y), z(z){} }; typedef point vec; int sgn(double x) { if (fabs(x) < eps) return 0; else if (x < 0) return -1; else return 1; } vec operator +(vec a, vec b) { return vec(a.x + b.x, a.y + b.y, a.z + b.z); } vec operator -(point a, point b) { return vec(a.x - b.x, a.y - b.y, a.z - b.z); } vec operator *(double p, vec a) { return vec(p*a.x, p*a.y, p*a.z); } vec operator /(vec a, double p) { return vec(a.x / p, a.y / p, a.z / p); } bool operator <(vec a, vec b) { if (sgn(a.x - b.x) < 0) return true; else if (sgn(a.x - b.x) == 0 && sgn(a.y - b.y) < 0) return true; else if (sgn(a.y - b.y) == 0 && sgn(a.z - b.z) < 0) return true; return false; } bool operator ==(vec a, vec b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0 && sgn(a.z - b.z) == 0; } double dot(vec a, vec b) { return a.x*b.x + a.y*b.y + a.z*b.z; } double len(vec a) { return sqrt(dot(a, a)); } vec cross(vec a, vec b) { return vec(a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x); } double point2face(point p, point a, point b, point c) { double test1 = fabs(dot(cross(a - b, a - c), a - p)); double test2 = len(cross(a - b, a - c)); return fabs(dot(cross(a - b, a - c), a - p)) / len(cross(a - b, a - c)); } struct face { point a; point b; point c; point p; face(point a = point(0, 0, 0), point b = point(0, 0, 0), point c = point(0, 0, 0), point p = point(0, 0, 0)) :a(a), b(b), c(c), p(p){} }; bool operator <(face s, face t) { return point2face(s.p, s.a, s.b, s.c) < point2face(s.p, s.a, s.b, s.c); } bool fourpinaface(point a, point b, point c, point d) { if (sgn(len(cross(cross(a - b, a - c), cross(a - b, a - d)))) == 0) { return true; } else return false; } double volume(point a, point b, point c, point d) { return abs(dot(cross(a - b, a - c), a - d) / 6); } double point2line(point p, point a, point b) { double test1 = len(cross(p - a, b - a)); double test2 = len(b - a); return len(cross(p - a, b - a)) / len(b - a); } point honface(point p, point a, point b, point c) { vec n = cross(a - b, a - c); if (dot(p - a, n) < 0) n = vec(0, 0, 0) - n; n = n / len(n); double t = point2face(p, a, b, c); return p - t*n; } bool hintri(point h, point a, point b, point c)//包含边上，给四边形让路 { double test1 = len(cross(a - b, a - c)); double test2 = len(cross(h - a, h - b)); double test3 = len(cross(h - b, h - c)); double test4 = len(cross(h - c, h - a)); double test5 = test1 - test2 - test3 - test4; if (sgn(len(cross(a - b, a - c)) - len(cross(h - a, h - b)) - len(cross(h - b, h - c)) - len(cross(h - c, h - a))) == 0) return true; else return false; } bool isconcave(point A, point B, point C, point D, point E) { double test1 = dot(cross(B - A, C - A), D - A); double test2 = dot(cross(B - A, C - A), E - A); return dot(cross(B - A, C - A), D - A)*dot(cross(B - A, C - A), E - A) < 0; } vector<double>dist; int main(void) { point A, B, C, D, E, F;//B,D,E作为一个平面 int T = 0; while (scanf("%lf%lf%lf", &A.x, &A.y, &A.z) == 3) { dist.clear(); scanf("%lf %lf %lf", &B.x, &B.y, &B.z); scanf("%lf %lf %lf", &C.x, &C.y, &C.z); scanf("%lf %lf %lf", &D.x, &D.y, &D.z); scanf("%lf %lf %lf", &E.x, &E.y, &E.z); scanf("%lf %lf %lf", &F.x, &F.y, &F.z); T++; double V1 = volume(A, B, C, D); double V2 = volume(A, B, C, E); double sumv = V1 + V2; point sumg = V1 / 4 * (A + B + C + D) + V2*(A + B + C + E) / 4; point G = sumg / sumv; if (isconcave(D, B, A, E, C) == true) { point h = honface(G, B, D, E); if (hintri(h, B, D, E) == true)//在边上应该是可以的吧 { if (point2line(h, B, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, B, D, E)); } } h = honface(G, A, D, E); if (hintri(h, A, D, E) == true) { if (point2line(h, A, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, A) >= 0.2) { dist.push_back(point2face(F, A, D, E)); } } } else if (fourpinaface(A, B, D, E) == true)//在某个三角形内，但是要找四个边的判断，不能简单的跟凹面合并！！！ { point h = honface(G, B, D, E); if (hintri(h, B, D, E) == true) { if (point2line(h, B, D) >= 0.2&&point2line(h, A, E) >= 0.2&&point2line(h, A, D) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, B, D, E)); } } h = honface(G, A, D, E); if (hintri(h, A, D, E) == true) { if (point2line(h, B, D) >= 0.2&&point2line(h, A, E) >= 0.2&&point2line(h, A, D) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, A, D, E)); } } } else { point h = honface(G, A, B, E); if (hintri(h, A, B, E) == true) { if (point2line(h, A, B) >= 0.2&&point2line(h, B, E) >= 0.2&&point2line(h, E, A) >= 0.2) { dist.push_back(point2face(F, A, B, E)); } } h = honface(G, A, B, D); if (hintri(h, A, B, D) == true) { if (point2line(h, A, B) >= 0.2&&point2line(h, B, D) >= 0.2&&point2line(h, D, A) >= 0.2) { dist.push_back(point2face(F, A, B, D)); } } } if (isconcave(D, B, C, A, E) == true) { point h = honface(G, B, D, E); if (hintri(h, B, D, E) == true) { if (point2line(h, B, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, B, D, E)); } } h = honface(G, C, D, E); if (hintri(h, C, D, E) == true) { if (point2line(h, C, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, C) >= 0.2) { dist.push_back(point2face(F, C, D, E)); } } } else if (fourpinaface(B, C, D, E) == true) { point h = honface(G, B, D, E); if (hintri(h, B, D, E) == true) { if (point2line(h, B, D) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, B, D, E)); } } h = honface(G, C, D, E); if (hintri(h, C, D, E) == true) { if (point2line(h, B, D) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, C, D, E)); } } } else { point h = honface(G, B, C, E); double test = dot(cross(B - C, B - E), B - h); if (hintri(h, B, C, E) == true) { if (point2line(h, B, C) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, E, B) >= 0.2) { dist.push_back(point2face(F, B, C, E)); } } h = honface(G, B, C, D); if (hintri(h, B, C, D) == true) { if (point2line(h, B, C) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, D, B) >= 0.2) { dist.push_back(point2face(F, B, C, D)); } } } if (isconcave(D, A, C, B, E) == true) { point h = honface(G, A, D, E); if (hintri(h, A, D, E) == true) { if (point2line(h, A, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, A) >= 0.2) { dist.push_back(point2face(F, A, D, E)); } } h = honface(G, C, D, E); if (hintri(h, C, D, E) == true) { if (point2line(h, C, D) >= 0.2&&point2line(h, D, E) >= 0.2&&point2line(h, E, C) >= 0.2) { dist.push_back(point2face(F, C, D, E)); } } } else if (fourpinaface(A, C, D, E) == true) { point h = honface(G, A, D, E); if (hintri(h, A, D, E) == true) { if (point2line(h, A, D) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, A, E) >= 0.2) { dist.push_back(point2face(F, A, D, E)); } } h = honface(G, C, D, E); if (hintri(h, C, D, E) == true) { if (point2line(h, A, D) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, E, A) >= 0.2) { dist.push_back(point2face(F, C, D, E)); } } } else { point h = honface(G, A, C, E); double test = dot(cross(A - C, A - E), A - h); if (hintri(h, A, C, E) == true) { if (point2line(h, A, C) >= 0.2&&point2line(h, C, E) >= 0.2&&point2line(h, E, A) >= 0.2) { dist.push_back(point2face(F, A, C, E)); } } h = honface(G, A, C, D); if (hintri(h, A, C, D) == true) { if (point2line(h, A, C) >= 0.2&&point2line(h, C, D) >= 0.2&&point2line(h, D, A) >= 0.2) { dist.push_back(point2face(F, A, C, D)); } } } sort(dist.begin(), dist.end()); printf("Case %d: %.5lf %.5lf\n", T, dist[0], dist[dist.size() - 1]); } return 0; }