Advertisement
Guest User

Untitled

a guest
May 27th, 2012
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.63 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <ctime>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <cassert>
  12. #include <queue>
  13. #include <string>
  14. #include <ctime>
  15. #include <stack>
  16.  
  17. #define sqr(x) ((x)*(x))
  18. #define sz(a) (int)a.size()
  19. #define pb push_back
  20. #define mp make_pair
  21. #define zero(a) memset (a, 0, sizeof(a))
  22. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  23.  
  24.  
  25. #if ( _WIN32 || __WIN32__ )
  26.     #define LLD "%I64d"
  27. #else
  28.     #define LLD "%lld"
  29. #endif
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef unsigned long long ull;
  35. typedef long double ld;
  36. typedef vector<int> vi;
  37. typedef vector<vi> vvi;
  38. typedef vector<bool> vb;
  39. typedef vector<vb> vvb;
  40.  
  41. #define taskname "worm"
  42.  
  43. const int inf = (int)1e9;
  44.  
  45. struct point{
  46.     int x,y,z;
  47.     point(){
  48.     }
  49.     point(int x,int y,int z):x(x),y(y),z(z){
  50.     }
  51. };
  52.  
  53. point operator-(const point& a,const point& b){
  54.     return point(a.x - b.x,a.y - b.y,a.z - b.z);
  55. }
  56.  
  57. int det(int a,int b,int c,int d){
  58.     return a*d - b*c;
  59. }
  60.  
  61. point operator*(const point& a,const point& b){
  62.     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));
  63. }
  64.  
  65.  
  66. struct plane{
  67.   ll a,b,c,d;
  68.   int id1,id2,id3;
  69.  
  70.   plane(){
  71.     a=b=c=d=0;
  72.   }
  73.   ll dist(point p){
  74.     return a*1LL*p.x+b*1LL*p.y+c*1LL*p.z+d;
  75.   }
  76.   ld rdist(point p){
  77.     return fabsl(dist(p))/sqrt(a*a+b*b+c*c);
  78.   }
  79.   plane(point A,point B,point C,int id1=-1,int id2=-1,int id3=-1){
  80.     this->id1 = id1;
  81.     this->id2 = id2;
  82.     this->id3 = id3;
  83.     point v = (C-A)*(B-A);
  84.     a = v.x;
  85.     b = v.y;
  86.     c = v.z;
  87.     d = -a*1LL*A.x -b*1LL*A.y -c*1LL*A.z;
  88.     #ifdef LOCAL
  89.         assert(dist(A) == 0);
  90.         assert(dist(B) == 0);
  91.         assert(dist(C) == 0);
  92.     #endif
  93.   }
  94.   void inverse(){
  95.     a*=-1;
  96.     b*=-1;
  97.     c*=-1;
  98.     d*=-1;
  99.   }
  100. };
  101.  
  102. vector<plane> v;
  103.  
  104. point p[1100];
  105. int n;
  106.  
  107.  
  108. int main (void)
  109. {
  110.   freopen (taskname".in", "r", stdin);
  111.   freopen (taskname".out", "w", stdout);
  112.   scanf("%d",&n);
  113.   for (int i = 0; i < n; i++)
  114.     scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
  115.  
  116.   for (int i = 0; i < 4; i++)
  117.     for (int j = i+1; j < 4; j++)
  118.         for (int k = j+1; k < 4; k++){
  119.             v.pb(plane(p[i],p[j],p[k],i,j,k));
  120.             if (v.back().dist(p[1+2+3-i-j-k]) < 0)
  121.                 v.back().inverse();
  122.         }
  123.  
  124.   for (int i = 4; i < n; i++){
  125.     vector<pair<int,int> > used;
  126.     for (int j = 0; j < (int)v.size(); j++){
  127.         if (v[j].dist(p[i]) < 0){    
  128.             used.pb(mp(v[j].id1,v[j].id2));
  129.             used.pb(mp(v[j].id1,v[j].id3));
  130.             used.pb(mp(v[j].id2,v[j].id3));
  131.             swap(v[j],v.back());
  132.             v.pop_back();
  133.             --j;
  134.         }
  135.     }
  136.     for (int j = 0; j < (int)used.size(); j++)
  137.         if (used[j].first > used[j].second)
  138.             swap(used[j].first,used[j].second);
  139.     sort(used.begin(),used.end());
  140.  
  141.     for (int j = 0; j < (int)used.size(); j++)
  142.         if ((!j || used[j] != used[j-1]) && (j == (int)used.size()-1 || used[j] != used[j+1])){
  143.             v.pb(plane(p[used[j].first],p[used[j].second],p[i],used[j].first,used[j].second,i));
  144.             for (int k = 0; k <= i; k++){
  145.                 if (v.back().dist(p[k]) > 0)
  146.                     break;
  147.                 if (v.back().dist(p[k]) < 0){
  148.                     v.back().inverse();
  149.                     break;
  150.                 }                  
  151.             }
  152.             #ifdef LOCAL
  153.                 for (int k = 0; k <= i; k++)
  154.                     assert(v.back().dist(p[i]) >= 0);
  155.             #endif
  156.         }
  157.   }
  158.  
  159.   int m;
  160.   scanf("%d",&m);
  161.  
  162.  
  163.   for (int i = 0; i < m; i++){
  164.     point p;
  165.     scanf("%d %d %d",&p.x,&p.y,&p.z);
  166.     ld res = 1e100;
  167.     for (int j = 0; j < (int)v.size(); j++)
  168.         res = min(res, v[j].rdist(p));
  169.     printf("%.7lf\n",(double)res);
  170.   }
  171.  
  172.            
  173.   return 0;
  174. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement