首页 > 代码库 > 2017-03-18 HDU 5733 计算几何 codeforces 599E 状压dp(待补)
2017-03-18 HDU 5733 计算几何 codeforces 599E 状压dp(待补)
HDU 5733
题意：给出四面体的四个顶点，求出其内切球的球心坐标和半径，如果不存在内切球，输出"O O O O"。
tags：一堆公式。。可以做模板了
我们可以将平面上的四点得到由同一个点出发的三个矢量。这样就可以计算这三个矢量的混合积M，则M/6即为四面体体积V。
题目无解的情况当且仅当四点共面，即混合积为0。
求得四面体体积后，可以根据公式r = 3V/(S1+S2+S3+S4)得到内切球半径, S1~S4为四面体四个面的面积。
当前的问题转化为如何求四面体四个面的面积。
由于我们已经知道四个顶点的坐标，因此可以通过海伦公式来分别求解四个面的面积S1~S4，以此来求得r。
对于球心坐标，有公式：
x=(p1.x*s1+p2.x*s2+p3.x*s3+p4.x*s4)/(s1+s2+s3+s4);
y=(p1.y*s1+p2.y*s2+p3.y*s3+p4.y*s4)/(s1+s2+s3+s4);
z=(p1.z*s1+p2.z*s2+p3.z*s3+p4.z*s4)/(s1+s2+s3+s4);
si为pi做顶点时，对应的底面的面积。
// HDU 5733 #include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 200005;const double eps=1e-8;double s[4], sum, x, y, z, v;struct Point { double x, y, z; Point operator - (const Point &b) const { //向量 a 与 b 的点积 return Point{x-b.x, y-b.y, z-b.z}; } Point operator ^ (const Point &b) const { //向量 a 与 b 的叉积 return Point{(y*b.z-z*b.y), (z*b.x-x*b.z), (x*b.y-y*b.x)}; }} p[4];int dcmp(double x) { // x为混合积，判正负，x==0表示4点共面 if(fabs(x)<eps) return 0; return x<0?-1:1;}double MixMul(Point a, Point b, Point c) { //求向量a,b,c的混合积 return a.x*b.y*c.z+a.y*b.z*c.x+a.z*b.x*c.y-a.x*b.z*c.y-a.y*b.x*c.z-a.z*b.y*c.x;}double dis(Point a, Point b) { //两点距离 return sqrt(pow(a.x-b.x, 2)+pow(a.y-b.y, 2)+pow(a.z-b.z, 2));}double Heron(double a, double b, double c) { //海伦公式求三角形面积 double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c));}double getsqr(Point a, Point b, Point c) { //通过海伦公式求三个向量构成的面的面积 return Heron(dis(a,b), dis(b,c), dis(a,c));}int main(){ while(~scanf("%lf %lf %lf", &p[0].x, &p[0].y, &p[0].z)) { rep(i,1,3) scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z); v=fabs(MixMul(p[0]-p[1], p[0]-p[2], p[0]-p[3])); if(dcmp(v)==0) { puts("O O O O"); continue; } s[3]=getsqr(p[0], p[1], p[2]); // 分别求出4个面的面积s[i] s[2]=getsqr(p[0], p[1], p[3]); s[1]=getsqr(p[0], p[2], p[3]); s[0]=getsqr(p[1], p[2], p[3]); sum=0; rep(i,0,3) s[i]=fabs(s[i]), sum+=s[i]; // sum为四个面的面积和，内切球半径 = v/2/sum x=y=z=0; rep(i,0,3) { x+=p[i].x*s[i]; y+=p[i].y*s[i]; z+=p[i].z*s[i]; } x/=sum, y/=sum, z/=sum; //内切球球心坐标公式 printf("%.4f %.4f %.4f %.4f\n", x, y, z, v/2/sum); } return 0;}
2017-03-18 HDU 5733 计算几何 codeforces 599E 状压dp(待补)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。