tetrahedron

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1057 Accepted Submission(s): 450

Problem Description

Given four points ABCD, if ABCD is a tetrahedron, calculate the inscribed sphere of ABCD.

Input

Multiple test cases (test cases

≤100).

Each test cases contains a line of 12 integers

[−1e6,1e6] indicate the coordinates of four vertices of ABCD.

Input ends by EOF.

Output

Print the coordinate of the center of the sphere and the radius, rounded to 4 decimal places.

If there is no such sphere, output "O O O O".

Sample Input

0 0 0 2 0 0 0 0 2 0 2 0 
0 0 0 2 0 0 3 0 0 4 0 0

Sample Output

0.4226 0.4226 0.4226 0.4226
O O O O

Author

HIT

Source

2016 Multi-University Training Contest 1

Recommend

wange2014

一道计算几何题，当时想到了但是没敢写，可能也是因为第一场吧，我们仨都比较懵。

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;
struct point
{
    double x,y,z;
    point () {}
    point(double _x,double _y,double _z)
    {
        x=_x;
        y=_y;
        z=_z;
    }
};
typedef point vec;
vec operator - (point a,point b)
{
    return vec(a.x-b.x , a.y-b.y , a.z-b.z);
}
double operator * (point a,point b)
{
   return a.xb.x+a.yb.y+a.zb.z;
}
vec operator / (point a,point b)
{
    return vec(a.yb.z-a.zb.y , a.zb.x-a.xb.z , a.xb.y-a.y*b.x);
}
double dis(point a , point b)
{
    double c=sqrt((a.x-b.x)(a.x-b.x)+(a.y-b.y)(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
    return c;
}
double Sq(double a, double b,double c)
{
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)(p-b)(p-c));
}
int main()
{
    point A,B,C,D,O;
    vec AB,AC,AD;
    double r,ab,ac,ad,bc,bd,cd,S1,S2,S3,S4,V;
    while(cin>>A.x>>A.y>>A.z>>B.x>>B.y>>B.z>>C.x>>C.y>>C.z>>D.x>>D.y>>D.z)
    {
        ab=dis(A,B);
        ac=dis(A,C);
        ad=dis(A,D);
        bc=dis(B,C);
        bd=dis(B,D);
        cd=dis(C,D);
        S1=Sq(ab,ac,bc);
        S2=Sq(ac,ad,cd);
        S3=Sq(ab,ad,bd);
        S4=Sq(bc,bd,cd);
        AB=A-B;
        AC=A-C;
        AD=A-D;
        V=abs(((AB/AC)AD)/6);
        if(V<=0)
        {
            cout<<"O O O O"<<endl;
            continue;
        }
        r=(3V)/(S1+S2+S3+S4);
        O.x=(S1D.x+S2B.x+S3C.x+S4A.x)/(S1+S2+S3+S4);
        O.y=(S1D.y+S2B.y+S3C.y+S4A.y)/(S1+S2+S3+S4);
        O.z=(S1D.z+S2B.z+S3C.z+S4A.z)/(S1+S2+S3+S4);
        cout<<fixed<<setprecision(4)<<O.x<<’ ‘<<O.y<<’ ‘<<O.z<<’ ‘<<r<<endl;
    }
    return 0;
}