Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <ctime>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <cassert>
- #include <queue>
- #include <string>
- #include <ctime>
- #include <stack>
- #define sqr(x) ((x)*(x))
- #define sz(a) (int)a.size()
- #define pb push_back
- #define mp make_pair
- #define zero(a) memset (a, 0, sizeof(a))
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #if ( _WIN32 || __WIN32__ )
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- #define taskname "worm"
- const int inf = (int)1e9;
- struct point{
- int x,y,z;
- point(){
- }
- point(int x,int y,int z):x(x),y(y),z(z){
- }
- };
- point operator-(const point& a,const point& b){
- return point(a.x - b.x,a.y - b.y,a.z - b.z);
- }
- int det(int a,int b,int c,int d){
- return a*d - b*c;
- }
- point operator*(const point& a,const point& b){
- return point(det(a.y,a.z,b.y,b.z),-det(a.x,a.z,b.x,b.z),det(a.x,b.x,a.y,b.y));
- }
- struct plane{
- ll a,b,c,d;
- int id1,id2,id3;
- plane(){
- a=b=c=d=0;
- }
- ll dist(point p){
- return a*1LL*p.x+b*1LL*p.y+c*1LL*p.z+d;
- }
- ld rdist(point p){
- return fabsl(dist(p))/sqrt(a*a+b*b+c*c);
- }
- plane(point A,point B,point C,int id1=-1,int id2=-1,int id3=-1){
- this->id1 = id1;
- this->id2 = id2;
- this->id3 = id3;
- point v = (C-A)*(B-A);
- a = v.x;
- b = v.y;
- c = v.z;
- d = -a*1LL*A.x -b*1LL*A.y -c*1LL*A.z;
- #ifdef LOCAL
- assert(dist(A) == 0);
- assert(dist(B) == 0);
- assert(dist(C) == 0);
- #endif
- }
- void inverse(){
- a*=-1;
- b*=-1;
- c*=-1;
- d*=-1;
- }
- };
- vector<plane> v;
- point p[1100];
- int n;
- int main (void)
- {
- freopen (taskname".in", "r", stdin);
- freopen (taskname".out", "w", stdout);
- scanf("%d",&n);
- for (int i = 0; i < n; i++)
- scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
- for (int i = 0; i < 4; i++)
- for (int j = i+1; j < 4; j++)
- for (int k = j+1; k < 4; k++){
- v.pb(plane(p[i],p[j],p[k],i,j,k));
- if (v.back().dist(p[1+2+3-i-j-k]) < 0)
- v.back().inverse();
- }
- for (int i = 4; i < n; i++){
- vector<pair<int,int> > used;
- for (int j = 0; j < (int)v.size(); j++){
- if (v[j].dist(p[i]) < 0){
- used.pb(mp(v[j].id1,v[j].id2));
- used.pb(mp(v[j].id1,v[j].id3));
- used.pb(mp(v[j].id2,v[j].id3));
- swap(v[j],v.back());
- v.pop_back();
- --j;
- }
- }
- for (int j = 0; j < (int)used.size(); j++)
- if (used[j].first > used[j].second)
- swap(used[j].first,used[j].second);
- sort(used.begin(),used.end());
- for (int j = 0; j < (int)used.size(); j++)
- if ((!j || used[j] != used[j-1]) && (j == (int)used.size()-1 || used[j] != used[j+1])){
- v.pb(plane(p[used[j].first],p[used[j].second],p[i],used[j].first,used[j].second,i));
- for (int k = 0; k <= i; k++){
- if (v.back().dist(p[k]) > 0)
- break;
- if (v.back().dist(p[k]) < 0){
- v.back().inverse();
- break;
- }
- }
- #ifdef LOCAL
- for (int k = 0; k <= i; k++)
- assert(v.back().dist(p[i]) >= 0);
- #endif
- }
- }
- int m;
- scanf("%d",&m);
- for (int i = 0; i < m; i++){
- point p;
- scanf("%d %d %d",&p.x,&p.y,&p.z);
- ld res = 1e100;
- for (int j = 0; j < (int)v.size(); j++)
- res = min(res, v[j].rdist(p));
- printf("%.7lf\n",(double)res);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement