題意：給出一個5個頂點的多面體以及多面體內一點P。求讓 多面體不同的方式（即以不同的面）放在地面上，設這個著地的面為A，多面體重心在A上的投影為B，在保證B在A內部且距離A的各個邊界不小于0.2的前提 下（否則這種放置方式就是不合法的），求P距離地面的最大最小距離為多少。

思路:

（1）判斷兩個點是不是在面的同一側；否則這個面就不能作為著地的面；

（2）計算重心；

（3）計算點在面的投影；

（4）計算點是否在面內；

（5）計算點到線的距離；

（6）計算點到面的距離。

特殊情況：四點共面當底面.

1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 5 const double eps = 1e-8; 6 int dcmp(double x) 7 { 8 if(fabs(x) < eps) return 0; 9 else return x < 0 ? -1 : 1; 10 } 11 12 struct Point3 13 { 14 double x, y, z; 15 Point3(double x=0, double y=0, double z=0):x(x),y(y),z(z) { } 16 }; 17 18 typedef Point3 Vector3; 19 20 Vector3 operator + (const Vector3& A, const Vector3& B) 21 { 22 return Vector3(A.x+B.x, A.y+B.y, A.z+B.z); 23 } 24 25 Vector3 operator - (const Point3& A, const Point3& B) 26 { 27 return Vector3(A.x-B.x, A.y-B.y, A.z-B.z); 28 } 29 30 Vector3 operator * (const Vector3& A, double p) 31 { 32 return Vector3(A.x*p, A.y*p, A.z*p); 33 } 34 35 Vector3 operator / (const Vector3& A, double p) 36 { 37 return Vector3(A.x/p, A.y/p, A.z/p); 38 } 39 40 double Dot(const Vector3& A, const Vector3& B) 41 { 42 return A.x*B.x + A.y*B.y + A.z*B.z; 43 } 44 double Length(const Vector3& A) 45 { 46 return sqrt(Dot(A, A)); 47 } 48 double Angle(const Vector3& A, const Vector3& B) 49 { 50 return acos(Dot(A, B) / Length(A) / Length(B)); 51 } 52 Vector3 Cross(const Vector3& A, const Vector3& B) 53 { 54 return Vector3(A.y*B.z - A.z*B.y, A.z*B.x - A.x*B.z, A.x*B.y - A.y*B.x); 55 } 56 double Area2(const Point3& A, const Point3& B, const Point3& C) 57 { 58 return Length(Cross(B-A, C-A)); 59 } 60 double Volume6(const Point3& A, const Point3& B, const Point3& C, const Point3& D) 61 { 62 return Dot(D-A, Cross(B-A, C-A)); 63 } 64 65 bool read_point3(Point3& p) 66 { 67 if(scanf("%lf%lf%lf", &p.x, &p.y, &p.z) != 3) return false; 68 return true; 69 } 70 71 // 點p到平面p0-n的距離。n必須為單位向量 72 double DistanceToPlane(const Point3& p, const Point3& p0, const Vector3& n) 73 { 74 return fabs(Dot(p-p0, n)); // 如果不取絕對值，得到的是有向距離 75 } 76 77 // 點p在平面p0-n上的投影。n必須為單位向量 78 Point3 GetPlaneProjection(const Point3& p, const Point3& p0, const Vector3& n) 79 { 80 return p-n*Dot(p-p0, n); 81 } 82 83 // 點P到直線AB的距離 84 double DistanceToLine(const Point3& P, const Point3& A, const Point3& B) 85 { 86 Vector3 v1 = B - A, v2 = P - A; 87 return Length(Cross(v1, v2)) / Length(v1); 88 } 89 90 // p1和p2是否在線段a-b的同側 91 bool SameSide(const Point3& p1, const Point3& p2, const Point3& a, const Point3& b) 92 { 93 return dcmp(Dot(Cross(b-a, p1-a), Cross(b-a, p2-a))) >= 0; 94 } 95 96 // 點在三角形P0, P1, P2中 97 bool PointInTri(const Point3& P, const Point3& P0, const Point3& P1, const Point3& P2) 98 { 99 return SameSide(P, P0, P1, P2) && SameSide(P, P1, P0, P2) && SameSide(P, P2, P0, P1); 100 } 101 102 // 四面體的重心 103 Point3 Centroid(const Point3& A, const Point3& B, const Point3& C, const Point3& D) 104 { 105 return (A + B + C + D)/4.0; 106 } 107 108 #include<algorithm> 109 //using namespace std; 110 111 // 判斷P是否在三角形A, B, C中，并且到三條邊的距離都至少為mindist。保證P, A, B, C共面 112 bool InsideWithMinDistance(const Point3& P, const Point3& A, const Point3& B, const Point3& C, double mindist) 113 { 114 if(!PointInTri(P, A, B, C)) return false; 115 if(DistanceToLine(P, A, B) < mindist) return false; 116 if(DistanceToLine(P, B, C) < mindist) return false; 117 if(DistanceToLine(P, C, A) < mindist) return false; 118 return true; 119 } 120 121 // 判斷P是否在凸四邊形ABCD（順時針或逆時針）中，并且到四條邊的距離都至少為mindist。保證P, A, B, C, D共面 122 bool InsideWithMinDistance(const Point3& P, const Point3& A, const Point3& B, const Point3& C, const Point3& D, double mindist) 123 { 124 if(!PointInTri(P, A, B, C)) return false; 125 if(!PointInTri(P, C, D, A)) return false; 126 if(DistanceToLine(P, A, B) < mindist) return false; 127 if(DistanceToLine(P, B, C) < mindist) return false; 128 if(DistanceToLine(P, C, D) < mindist) return false; 129 if(DistanceToLine(P, D, A) < mindist) return false; 130 return true; 131 } 132 133 int main() 134 { 135 for(int kase = 1; ; kase++) 136 { 137 Point3 P[5], F; 138 for(int i = 0; i < 5; i++) 139 if(!read_point3(P[i])) return 0; 140 read_point3(F); 141 142 // 求重心坐標 143 Point3 c1 = Centroid(P[0], P[1], P[2], P[3]); 144 Point3 c2 = Centroid(P[0], P[1], P[2], P[4]); 145 double vol1 = fabs(Volume6(P[0], P[1], P[2], P[3])) / 6.0; 146 double vol2 = fabs(Volume6(P[0], P[1], P[2], P[4])) / 6.0; 147 Point3 centroid = (c1 * vol1 + c2 * vol2) / (vol1 + vol2); 148 149 // 枚舉放置方案 150 double mindist = 1e9, maxdist = -1e9; 151 for(int i = 0; i < 5; i++) 152 for(int j = i+1; j < 5; j++) 153 for(int k = j+1; k < 5; k++) 154 { 155 // 找出另外兩個點的下標a和b 156 int vis[5] = {0}; 157 vis[i] = vis[j] = vis[k] = 1; 158 int a, b; 159 for(a = 0; a < 5; a++) if(!vis[a]) 160 { 161 b = 10-i-j-k-a; 162 break; 163 } 164 165 // 判斷a和b是否在平面i-j-k的異側(體積法判斷) 166 int d1 = dcmp(Volume6(P[i], P[j], P[k], P[a])); 167 int d2 = dcmp(Volume6(P[i], P[j], P[k], P[b])); 168 if(d1 * d2 < 0) continue; // 是，則放置方案不合法 169 170 Vector3 n = Cross(P[j]-P[i], P[k]-P[i]); // 法向量 171 n = n / Length(n); // 單位化 172 173 Point3 proj = GetPlaneProjection(centroid, P[i], n); // 重心在平面i-j-k上的投影 174 bool ok = InsideWithMinDistance(proj, P[i], P[j], P[k], 0.2); 175 if(!ok) 176 { 177 if(d1 == 0) // i-j-k-a四點共面。i和j一定為ABC三個頂點之一，k和a是D或者E 178 { 179 if(!InsideWithMinDistance(proj, P[i], P[k], P[j], P[a], 0.2)) continue; 180 } 181 else if(d2 == 0) // i-j-k-b四點共面。i和j一定為ABC三個頂點之一，k和b是D或者E 182 { 183 if(!InsideWithMinDistance(proj, P[i], P[k], P[j], P[b], 0.2)) continue; 184 } 185 else 186 continue; 187 } 188 189 // 更新答案 190 double dist = DistanceToPlane(F, P[i], n); 191 mindist = min(mindist, dist); 192 maxdist = max(maxdist, dist); 193 } 194 printf("Case %d: %.5lf %.5lf\n", kase, mindist, maxdist); 195 } 196 return 0; 197 } View Code

?

轉載于:https://www.cnblogs.com/ITUPC/p/4906974.html

總結

以上是生活随笔為你收集整理的uvalive 4795 Paperweight的全部內容，希望文章能夠幫你解決所遇到的問題。

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