#include "stdio.h"
#include <cmath>
double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);
double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];
double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
{
double r = 0;
//calculation of three vectors
//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);
//calculation of supporting scalar variables
//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
double a, b, c, d, e;
a = dot(u,u); // a=u^2;
b = dot(u,v);
c = dot(v,v); // c=v^2;
d = dot(u,w0);
e = dot(v,w0);
//calculation of main determinant
// D = b^2 - a*c
double D = b*b - a*c;
if (D == 0) //lines are parallel
{
double t0=-e/c; double t1=-e/c; double s0 = (-e+b)/c ; double s1= (e-c)*b/(c*a);
if (in(t0) || in(t1) || in(s0) || in(s1))
{
double wq[4];
prod(e/c,v, wq); //projection w0 on line q
double wd[4];
diff(w0,wq, wd);
r = abs(wd);
return r ; //r = |w0 - wq|
}
//else minimal distance between segments equals minimal distance between ends of segments
r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
return r;
}
// else lines are not parallel
{
//calculation of determinants
double D1 = b*e - c*d, D2 = a*e - b*d;
//calculation of parameters for minimal segment between lines
double sc = D1/D, tc = D2/D;
if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
{
return r = sd(sc,tc); // r = |wc|
}
//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
{
double t1 = 0, s1=_(d/a);
double t2 = _(-2*e/c), s2=0;
double t3 = 1, s3=_(2*(b+d)/a);
double t4 = _(2*(b+e)/c), s4=0;
return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));
}
}
}
int main()
{
scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
printf("%lf\n", InterSegmentDistance4d());
return 0;
}
double dot(double * u, double * v)//calculing the scalar production of two vectors
{
return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
}
double abs(double * u)//finding the length of vector
{
return sqrt(dot(u,u));
}
double min(double a, double b, double c, double d)//finding the minimal value
{
double m = a;
if(m>b) m = b;
if(m>c) m = c;
if(m>d) m = d;
return m;
}
void diff(double * a, double * b, double * c)//finding the difference of two 4d objects(dots or vectors)
{
c[0]=a[0]-b[0];
c[1]=a[1]-b[1];
c[2]=a[2]-b[2];
c[3]=a[3]-b[3];
}
void summ(double * a, double * b, double * c)//finding the sum of two 4d objects(dots or vecrors)
{
c[0]=a[0]+b[0];
c[1]=a[1]+b[1];
c[2]=a[2]+b[2];
c[3]=a[3]+b[3];
}
void prod(double k, double * u, double * v)//calculing the production of vector and number
{
v[0] = k * u[0];
v[1] = k * u[1];
v[2] = k * u[2];
v[3] = k * u[3];
}
bool in(double s)//checking if the vatue is between 0 and 1
{
return 0 <= s && s <= 1 ;
}
bool in(double s, double t)//variation of the previous function for two values
{
return in(t) && in(s);
}
double sd(double s, double t)//finding the distance between two segments using two parameters s and t
{
double Pc[4], Qc[4], W[4];
prod(s,u, Pc);
summ(Pc,P0, Pc);
prod(t,v, Qc);
summ(Qc,Q0, Qc);
diff(Qc, Pc, W);
return abs(W);
}
double _(double s)//restriction the value for the interval [0,1]
{
double s1 = s;
if(s > 1)s1 = 1;
if(s < 0)s1 = 0;
return s1;
}
I2luY2x1ZGUgInN0ZGlvLmgiCiNpbmNsdWRlIDxjbWF0aD4KCmRvdWJsZSBkb3QoZG91YmxlICogdSwgZG91YmxlICogdik7CmRvdWJsZSBhYnMoZG91YmxlICogdSk7CmRvdWJsZSBtaW4oZG91YmxlIGEsIGRvdWJsZSBiLCBkb3VibGUgYywgZG91YmxlIGQpOwp2b2lkIHByb2QoZG91YmxlIGssIGRvdWJsZSAqIHUsIGRvdWJsZSAqIHYpOwp2b2lkIGRpZmYoZG91YmxlICogYSwgZG91YmxlICogYiwgZG91YmxlICogYyk7CnZvaWQgc3VtbShkb3VibGUgKiBhLCBkb3VibGUgKiBiLCBkb3VibGUgKiBjKTsKYm9vbCBpbihkb3VibGUgcyk7CmJvb2wgaW4oZG91YmxlIHMsIGRvdWJsZSB0KTsKZG91YmxlIHNkKGRvdWJsZSBzLCBkb3VibGUgdCk7CmRvdWJsZSBfKGRvdWJsZSBzKTsKCmRvdWJsZSBQMFs0XSxQMVs0XSxRMFs0XSxRMVs0XTsKZG91YmxlIHVbNF0sdls0XSx3MFs0XTsKCmRvdWJsZSBJbnRlclNlZ21lbnREaXN0YW5jZTRkKCkKLy9pbnB1dDogZm91ciA0ZCBwb2ludHMgUDAsIFAxLCBRMCwgUTEKLy8gb3V0cHV0OiByID0gbWluaW1hbCBkaXN0YW5jZSBiZXR3ZWVuIGxpbmVzIHNlZ21lbnRzIFAwUDEgYW5kIFEwUTEKICAgIHsKICAgICAgZG91YmxlIHIgPSAwOwogICAgICAvL2NhbGN1bGF0aW9uIG9mIHRocmVlIHZlY3RvcnMKCSAgLy91ID0gUDEgLSBQMCwgdiA9IFExIC0gUTAsIHcwID0gUTAgLSBQMAogICAgICAgICAgZGlmZihQMSwgUDAsIHUpOyAgZGlmZihRMSwgUTAsIHYpOyAgZGlmZihRMCwgUDAsIHcwKTsKCSAgIC8vY2FsY3VsYXRpb24gb2Ygc3VwcG9ydGluZyBzY2FsYXIgdmFyaWFibGVzCgkgICAgLy9hID0gdSp1LCBiID0gdSp2LCBjID0gdip2LCBkID0gdzAqdSwgZSA9IHcwKnYKCSAgICBkb3VibGUgIGEsIGIsIGMsIGQsIGU7CiAgICAJICAgICAgICBhID0gZG90KHUsdSk7ICAvLyBhPXVeMjsKCSAgICAgICAgICAgIGIgPSBkb3QodSx2KTsKCSAgICAgICAgICAgIGMgPSBkb3Qodix2KTsgIC8vIGM9dl4yOwoJICAgICAgICAgICAgZCA9IGRvdCh1LHcwKTsKCSAgICAgICAgICAgIGUgPSBkb3Qodix3MCk7CgkgLy9jYWxjdWxhdGlvbiBvZiBtYWluIGRldGVybWluYW50CgkgICAgIC8vIEQgPSBiXjIgLSBhKmMKCSAgICAgIGRvdWJsZSBEID0gYipiIC0gYSpjOwoJICAgICAgaWYgKEQgPT0gMCkgLy9saW5lcyBhcmUgcGFyYWxsZWwKICAgICAgICAgICAgewogICAgICAgICAgICAgZG91YmxlIHQwPS1lL2M7IGRvdWJsZSB0MT0tZS9jOyBkb3VibGUgczAgPSAoLWUrYikvYyA7IGRvdWJsZSBzMT0gKGUtYykqYi8oYyphKTsKICAgICAgICAgICAgaWYgKGluKHQwKSB8fCBpbih0MSkgfHwgaW4oczApIHx8IGluKHMxKSkKICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgZG91YmxlIHdxWzRdOwogICAgICAgICAgICAgICAgICBwcm9kKGUvYyx2LCAgd3EpOyAgLy9wcm9qZWN0aW9uIHcwIG9uIGxpbmUgcQogICAgICAgICAgICAgICAgICBkb3VibGUgd2RbNF07CiAgICAgICAgICAgICAgICAgICBkaWZmKHcwLHdxLCAgd2QpOwogICAgICAgICAgICAgICAgICAgIHIgPSBhYnMod2QpOwogICAgICAgICAgICAgICAgICAgICByZXR1cm4gciA7IC8vciA9IHx3MCAtIHdxfAogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAvL2Vsc2UgbWluaW1hbCBkaXN0YW5jZSBiZXR3ZWVuIHNlZ21lbnRzIGVxdWFscyBtaW5pbWFsIGRpc3RhbmNlIGJldHdlZW4gZW5kcyBvZiBzZWdtZW50cwogICAgICAgICAgICAgICAgICAgICByID0gbWluKHNkKDAsMCksIHNkKDAsMSksIHNkKDEsMCksIHNkKDEsMSkpOwoJCSAgICAgICAgICAgICByZXR1cm4gcjsKICAgICAgICAgICAgfQoJICAgICAgIC8vIGVsc2UgbGluZXMgYXJlIG5vdCBwYXJhbGxlbAoJICAgICAgICB7CiAgICAgICAgICAgICAgICAvL2NhbGN1bGF0aW9uIG9mIGRldGVybWluYW50cwoJCSAgICBkb3VibGUgRDEgPSBiKmUgLSBjKmQsICBEMiA9IGEqZSAtIGIqZDsKCQkgICAgLy9jYWxjdWxhdGlvbiBvZiBwYXJhbWV0ZXJzIGZvciBtaW5pbWFsIHNlZ21lbnQgYmV0d2VlbiBsaW5lcwogICAgICAgICAgICBkb3VibGUgc2MgPSBEMS9ELCB0YyA9IEQyL0Q7CiAgICAgICAgICAgICBpZihpbihzYyx0YykpIC8vbWluaW1hbCBkaXN0YW5jZSBiZXR3ZWVuIHNlZ21lbnRzIGVxdWFscyBtaW5pbWFsIGRpc3RhbmNlIGJldHdlZW4gbGluZXMKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgIHJldHVybiByID0gc2Qoc2MsdGMpOyAvLyByID0gfHdjfAogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgLy9lbHNlIG1pbmltYWwgc2VnbWVudCBpcyBkZWZpbmVkIGJ5IHNvbWUgcGFyYW1ldGVyIHBvaW50IChzLHQpIG9uIGVkZ2Ugb2Ygc3F1YXJlIFswLDFdeFswLDFdCiAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGRvdWJsZSB0MSA9IDAsICAgczE9XyhkL2EpOwogICAgICAgICAgICAgICAgICAgIGRvdWJsZSB0MiA9IF8oLTIqZS9jKSwgczI9MDsKICAgICAgICAgICAgICAgICAgICBkb3VibGUgdDMgPSAxLCAgIHMzPV8oMiooYitkKS9hKTsKICAgICAgICAgICAgICAgICAgICBkb3VibGUgdDQgPSBfKDIqKGIrZSkvYyksIHM0PTA7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG1pbihzZChzMSx0MSksIHNkKHMyLHQyKSxzZChzMyx0MyksIHNkKHM0LHQ0KSk7CiAgICAgICAgICAgICAgICAgfQoJICAgICAgICB9CiAgICB9CgppbnQgbWFpbigpCnsKCXNjYW5mKCIlbGYgJWxmICVsZiAlbGYiLCZQMFswXSwgJlAwWzFdLCAmUDBbMl0sJlAwWzNdKTsKCXNjYW5mKCIlbGYgJWxmICVsZiAlbGYiLCZQMVswXSwgJlAxWzFdLCAmUDFbMl0sJlAxWzNdKTsKc2NhbmYoIiVsZiAlbGYgJWxmICVsZiIsJlEwWzBdLCAmUTBbMV0sICZRMFsyXSwmUTBbM10pOwoJc2NhbmYoIiVsZiAlbGYgJWxmICVsZiIsJlExWzBdLCAmUTFbMV0sICZRMVsyXSwmUTFbM10pOwogICAgICAgIHByaW50ZigiJWxmXG4iLCBJbnRlclNlZ21lbnREaXN0YW5jZTRkKCkpOwogICAgICAgIHJldHVybiAwOwp9Cgpkb3VibGUgZG90KGRvdWJsZSAqIHUsIGRvdWJsZSAqIHYpLy9jYWxjdWxpbmcgdGhlIHNjYWxhciBwcm9kdWN0aW9uIG9mIHR3byB2ZWN0b3JzCnsKICAgIHJldHVybiB1WzBdKnZbMF0rdVsxXSp2WzFdK3VbMl0qdlsyXSt1WzNdKnZbM107Cn0KCmRvdWJsZSBhYnMoZG91YmxlICogdSkvL2ZpbmRpbmcgdGhlIGxlbmd0aCBvZiB2ZWN0b3IKewogICAgcmV0dXJuIHNxcnQoZG90KHUsdSkpOwp9Cgpkb3VibGUgbWluKGRvdWJsZSBhLCBkb3VibGUgYiwgZG91YmxlIGMsIGRvdWJsZSBkKS8vZmluZGluZyB0aGUgbWluaW1hbCB2YWx1ZQp7CiAgICBkb3VibGUgbSA9IGE7CiAgICAgaWYobT5iKSBtID0gYjsKICAgICAgaWYobT5jKSBtID0gYzsKICAgICAgIGlmKG0+ZCkgbSA9IGQ7CiAgICAgICAgcmV0dXJuIG07Cn0KCnZvaWQgZGlmZihkb3VibGUgKiBhLCBkb3VibGUgKiBiLCBkb3VibGUgKiBjKS8vZmluZGluZyB0aGUgZGlmZmVyZW5jZSBvZiB0d28gNGQgb2JqZWN0cyhkb3RzIG9yIHZlY3RvcnMpCnsKCWNbMF09YVswXS1iWzBdOwoJY1sxXT1hWzFdLWJbMV07CgljWzJdPWFbMl0tYlsyXTsKCWNbM109YVszXS1iWzNdOwp9Cgp2b2lkIHN1bW0oZG91YmxlICogYSwgZG91YmxlICogYiwgZG91YmxlICogYykvL2ZpbmRpbmcgdGhlIHN1bSBvZiB0d28gNGQgb2JqZWN0cyhkb3RzIG9yIHZlY3JvcnMpCnsKCWNbMF09YVswXStiWzBdOwoJY1sxXT1hWzFdK2JbMV07CgljWzJdPWFbMl0rYlsyXTsKCWNbM109YVszXStiWzNdOwp9Cgp2b2lkIHByb2QoZG91YmxlIGssIGRvdWJsZSAqIHUsIGRvdWJsZSAqIHYpLy9jYWxjdWxpbmcgdGhlIHByb2R1Y3Rpb24gb2YgdmVjdG9yIGFuZCBudW1iZXIKewogdlswXSA9IGsgKiB1WzBdOwogdlsxXSA9IGsgKiB1WzFdOwogdlsyXSA9IGsgKiB1WzJdOwogdlszXSA9IGsgKiB1WzNdOwp9Cgpib29sIGluKGRvdWJsZSBzKS8vY2hlY2tpbmcgaWYgdGhlIHZhdHVlIGlzIGJldHdlZW4gMCBhbmQgMQogewogICAgcmV0dXJuIDAgPD0gcyAmJiBzIDw9IDEgOwogfQoKYm9vbCBpbihkb3VibGUgcywgZG91YmxlIHQpLy92YXJpYXRpb24gb2YgdGhlIHByZXZpb3VzIGZ1bmN0aW9uIGZvciB0d28gdmFsdWVzCnsKICAgIHJldHVybiAgaW4odCkgJiYgaW4ocyk7Cn0KCmRvdWJsZSBzZChkb3VibGUgcywgZG91YmxlIHQpLy9maW5kaW5nIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBzZWdtZW50cyB1c2luZyB0d28gcGFyYW1ldGVycyBzIGFuZCB0CnsKICAgIGRvdWJsZSBQY1s0XSwgUWNbNF0sIFdbNF07CiAgICAgcHJvZChzLHUsIFBjKTsKICAgICAgc3VtbShQYyxQMCwgUGMpOwogICAgIHByb2QodCx2LCBRYyk7CiAgICAgIHN1bW0oUWMsUTAsIFFjKTsKICAgICAgIGRpZmYoUWMsIFBjLCBXKTsKICAgICAgICByZXR1cm4gIGFicyhXKTsKfQoKZG91YmxlIF8oZG91YmxlIHMpLy9yZXN0cmljdGlvbiB0aGUgdmFsdWUgZm9yIHRoZSBpbnRlcnZhbCBbMCwxXQp7CiAgIGRvdWJsZSBzMSA9IHM7CiAgIGlmKHMgPiAxKXMxID0gMTsKICAgaWYocyA8IDApczEgPSAwOwogICAgcmV0dXJuIHMxOwp9