Find the Gap

Find the Gap - 题目 - QOJ.ac

---

题型分析

三位向量基本运算

题目描述

给出空间上的一系列点，求出两个平行面的最短距离，使得这两个平行面能把所有的点包括在内。

题解

用 $O(n^2)$ 枚举每两个点构成的向量，做出两两向量之间的叉乘，也即两个向量的法向量

之后枚举所有的点在法向量上的最长投影和最短投影（注意投影有向），两个投影之差的最小值就是答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=60;
#define IN inline
struct Point{
	double x,y,z;
	IN Point operator+(const Point &t)const{return {x+t.x,y+t.y,z+t.z};}
	IN Point operator-(const Point &t)const{return {x-t.x,y-t.y,z-t.z};}
	IN Point operator*(const Point &t)const{return {y*t.z-z*t.y,z*t.x-x*t.z,x*t.y-y*t.x};}
	IN Point operator*(const double &t)const{return{x*t,y*t,z*t};}
	IN double operator^(const Point &t)const{return x*t.x+y*t.y+z*t.z;}
}a[maxn];
IN double sqr(double x){return x*x;}
IN double dis(Point a){return sqr(a.x)+sqr(a.y)+sqr(a.z);}

double ans=1e18;
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			Point A=a[i]-a[j];
			for(int k=1;k<=n;++k){
				for(int k1=1;k1<=n;++k1){
					Point B=a[k]-a[k1];
					Point no=A*B;
					double d=dis(no);
					if(d==0)continue;
					double h1=no^a[1],h2=no^a[1];
					for(int m=1;m<=n;++m){
						h1=min(h1,no^a[m]);
						h2=max(h2,no^a[m]);
					}
					ans=min(ans,fabs(h1-h2)/sqrt(d));
				}
			}
		}
	}
	cout<<fixed<<setprecision(15);
	if(ans==1e18)ans=0;
	cout<<ans<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
	int T=1;
	while(T--)solve();
}