NC17378. Rescue
描述
输入描述
The first line contains an integer T (1 ≤ T ≤ 100000), indicating the number of test cases.
Each case contains two line. The first line contains six integers x1, y1, z1, x2, y2, z2 (-100 ≤ x1,y1,z1,x2,y2,z2 ≤ 100), correspondingly indicating two endpoints of the first spaceship. The second line contains six integers in the same format, describing the second spaceship.
输出描述
For each test cases, output one line indicating the squared length of shortest tunnel. Keep 30 decimal places.
示例1
输入:
2 0 0 0 1 1 1 1 1 1 2 2 2 1 0 0 0 1 0 1 1 0 2 2 0
输出:
0.000000000000000000000000000000 0.500000000000000000000000000000
说明:
Please round to 30 decimal places, without extra spaces.C++14(g++5.4) 解法, 执行用时: 566ms, 内存消耗: 3808K, 提交时间: 2018-08-05 13:39:11
#include<bits/stdc++.h>
#define N 10010
#define LL long long
using namespace std;
struct Point
{
LL x,y,z;
Point(LL x=0,LL y=0,LL z=0):x(x),y(y),z(z){};
void read(){cin>>x>>y>>z;}
};
typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y,a.z+b.z);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y,a.z-b.z);}
bool operator == (Vector a,Vector b){return a.x==b.x && a.y==b.y && a.z==b.z;}
LL Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y+a.z*b.z;} //点积
LL Length(Vector a){return Dot(a,a);}
Vector Cross(Vector a,Vector b) //叉积
{return Vector(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);}
LL z[5][2];
void spy(int x,Point p,Point a,Point b)
{
if(a==b)
{
z[x][0]=Length(p-a);z[x][1]=1;
return;
}
Vector v1=b-a,v2=p-a,v3=p-b;
if (Dot(v1,v2)<0) {z[x][0]=Length(v2);z[x][1]=1;}else
if (Dot(v1,v3)>0) {z[x][0]=Length(v3);z[x][1]=1;}else
{
z[x][0]=Length(Cross(v1,v2));z[x][1]=Length(v1);
}
}
void print(LL x,LL y)
{
int a[40];
cout<<x/y<<".";
LL t=x%y;
for (int i=0;i<30;i++)
{
t*=10;
a[i]=t/y;
t=t%y;
}
if(t*10/y>=5)a[29]++;
int i=29;
while(a[i]==10) {a[i]=0;a[--i]++;}
for (int i=0;i<30;i++)cout<<a[i];cout<<endl;
}
int main()
{
int T;
cin>>T;
Point a,b,aa,bb;
while(T--)
{
a.read();b.read();aa.read();bb.read();
Vector n=Cross(a-b,aa-bb);
Vector p1=Cross(b-a,n),p2=Cross(bb-aa,n);
if (Dot(aa-a,p1)*Dot(bb-a,p1)<0 && Dot(a-aa,p2)*Dot(b-aa,p2)<0)
{
Vector v=Cross(a-b,aa-bb);
if (Length(v)==0)
{
cout<<"0.000000000000000000000000000000"<<endl;
}else
{
LL ff=Dot(a-aa,v);
LL n=Length(v);
print(ff*ff,n);
}
}else
{
spy (1,a,aa,bb);
spy (2,b,aa,bb);
spy (3,aa,a,b);
spy (4,bb,a,b);
for (int i=2;i<=4;i++)
{
if (z[1][0]*z[i][1]>z[1][1]*z[i][0])
{
swap(z[1][0],z[i][0]);
swap(z[1][1],z[i][1]);
}
}
print(z[1][0],z[1][1]);
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 567ms, 内存消耗: 3672K, 提交时间: 2018-08-05 16:47:59
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct Point
{
LL x,y,z;
Point(LL x=0,LL y=0,LL z=0):x(x),y(y),z(z){};
void read(){cin>>x>>y>>z;}
};
typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y,a.z+b.z);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y,a.z-b.z);}
bool operator == (Vector a,Vector b){return a.x==b.x && a.y==b.y && a.z==b.z;}
LL Dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y+a.z*b.z;
}
LL Length(Vector a){
return Dot(a,a);
}
Vector Cross(Vector a,Vector b){
return Vector(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
LL z[5][2];
void sp(int x,Point p,Point a,Point b)
{
if(a==b)
{
z[x][0]=Length(p-a);z[x][1]=1;
return;
}
Vector v1=b-a,v2=p-a,v3=p-b;
if (Dot(v1,v2)<0) {z[x][0]=Length(v2);z[x][1]=1;}else
if (Dot(v1,v3)>0) {z[x][0]=Length(v3);z[x][1]=1;}else
{
z[x][0]=Length(Cross(v1,v2));z[x][1]=Length(v1);
}
}
void print(LL x,LL y)
{
int a[40];
cout<<x/y<<".";
LL t=x%y;
for (int i=0;i<30;i++)
{
t*=10;
a[i]=t/y;
t=t%y;
}
if(t*10/y>=5)a[29]++;
int i=29;
while(a[i]==10) {a[i]=0;a[--i]++;}
for (int i=0;i<30;i++)cout<<a[i];cout<<endl;
}
int main()
{
int T;
cin>>T;
Point a,b,aa,bb;
while(T--)
{
a.read();b.read();aa.read();bb.read();
Vector n=Cross(a-b,aa-bb);
Vector p1=Cross(b-a,n),p2=Cross(bb-aa,n);
if (Dot(aa-a,p1)*Dot(bb-a,p1)<0 && Dot(a-aa,p2)*Dot(b-aa,p2)<0)
{
Vector v=Cross(a-b,aa-bb);
if (Length(v)==0)
{
cout<<"0.000000000000000000000000000000"<<endl;
}else
{
LL ff=Dot(a-aa,v);
LL n=Length(v);
print(ff*ff,n);
}
}else
{
sp (1,a,aa,bb);
sp (2,b,aa,bb);
sp (3,aa,a,b);
sp (4,bb,a,b);
for (int i=2;i<=4;i++)
{
if (z[1][0]*z[i][1]>z[1][1]*z[i][0])
{
swap(z[1][0],z[i][0]);
swap(z[1][1],z[i][1]);
}
}
print(z[1][0],z[1][1]);
}
}
return 0;
}