Advertisement
Guest User

Untitled

a guest
May 27th, 2012
265
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.84 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:64000000")
  2. #define _CRT_SECURE_NO_DEPRECATE
  3. #include <cmath>
  4. #include <cassert>
  5. #include <cstdio>
  6. #include <ctime>
  7. #include <iostream>
  8. #include <sstream>
  9. #include <map>
  10. #include <set>
  11. #include <vector>
  12. #include <string>
  13. #include <queue>
  14. #include <deque>
  15. #include <algorithm>
  16. #include <stack>
  17.  
  18. using namespace std;
  19.  
  20. #define mp make_pair
  21. #define pb push_back
  22. #define all(v) v.begin(), v.end()
  23.  
  24. #define forn(i, n) for (int i = 0; i < (int)(n); i++)
  25. #define for1(i, n) for (int i = 1; i <= (int)(n); i++)
  26. #define forv(i, v) forn(i, v.size())
  27.  
  28. typedef pair<int, int> pii;
  29. typedef long long ll;
  30.  
  31. #define NMAX 1005
  32.  
  33. struct Point
  34. {
  35. int x, y, z;
  36. };
  37.  
  38. Point center;
  39.  
  40. int used[NMAX][NMAX];
  41.  
  42. ll det(ll x1, ll y1, ll x2, ll y2)
  43. {
  44. return x1 * y2 - x2 * y1;
  45. }
  46.  
  47. struct Plane
  48. {
  49. ll a, b, c, d;
  50.  
  51. Plane() {};
  52.  
  53. Plane(Point& p1, Point& p2, Point& p3)
  54. {
  55. a = det(p1.y - p2.y, p3.y - p1.y, p1.z - p2.z, p3.z - p1.z);
  56. b = det(p1.z - p2.z, p3.z - p1.z, p1.x - p2.x, p3.x - p1.x);
  57. c = det(p1.x - p2.x, p3.x - p1.x, p1.y - p2.y, p3.y - p1.y);
  58. d = -(a * p1.x + b * p1.y + c * p1.z);
  59.  
  60. if (a * center.x + b * center.y + c * center.z + 4 * d < 0)
  61. {
  62. a = -a;
  63. b = -b;
  64. c = -c;
  65. d = -d;
  66. }
  67. }
  68. };
  69.  
  70. Point p[NMAX];
  71.  
  72. struct Triangle
  73. {
  74. vector<int> v;
  75. Plane s;
  76.  
  77. Triangle() {};
  78. Triangle(int i, int j, int k)
  79. {
  80. v.pb(i);
  81. v.pb(j);
  82. v.pb(k);
  83. forv(i1, v)
  84. {
  85. forv(i2, v)
  86. {
  87. if (v[i1] < v[i2]) used[v[i1]][v[i2]]++;
  88. }
  89. }
  90. s = Plane(p[i], p[j], p[k]);
  91. }
  92. };
  93.  
  94. vector<Triangle> ch;
  95. int n;
  96.  
  97. bool inside(Plane& s, Point& p)
  98. {
  99. return s.a * p.x + s.b * p.y + s.c * p.z + s.d > 0;
  100. }
  101.  
  102. void add_point(int id)
  103. {
  104. vector<bool> deleted(ch.size(), false);
  105. vector<pii> edges;
  106.  
  107. forv(i, ch)
  108. {
  109. if (!inside(ch[i].s, p[id]))
  110. {
  111. deleted[i] = true;
  112. forv(j, ch[i].v)
  113. {
  114. forv(k, ch[i].v)
  115. {
  116. if (ch[i].v[j] < ch[i].v[k])
  117. {
  118. used[ch[i].v[j]][ch[i].v[k]]--;
  119. edges.pb(mp(ch[i].v[j], ch[i].v[k]));
  120. }
  121. }
  122. }
  123. }
  124. }
  125.  
  126. int k = 0;
  127. forv(i, ch)
  128. {
  129. if (!deleted[i])
  130. {
  131. ch[k++] = ch[i];
  132. }
  133. }
  134. ch.resize(k);
  135.  
  136. forv(i, edges)
  137. {
  138. if (used[edges[i].first][edges[i].second] == 1)
  139. {
  140. ch.pb(Triangle(id, edges[i].first, edges[i].second));
  141. }
  142. }
  143. }
  144.  
  145. double dist(Plane& s, Point& p)
  146. {
  147. return (s.a * p.x + s.b * p.y + s.c * p.z + s.d) / sqrt(double(s.a * s.a + s.b * s.b + s.c * s.c));
  148. }
  149. int main()
  150. {
  151. freopen("worm.in", "rt", stdin);
  152. freopen("worm.out", "wt", stdout);
  153.  
  154. scanf("%d", &n);
  155. forn(i, n)
  156. {
  157. scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
  158. }
  159.  
  160. forn(i, 4)
  161. {
  162. center.x += p[i].x;
  163. center.y += p[i].y;
  164. center.z += p[i].z;
  165. }
  166.  
  167. ch.pb(Triangle(0, 1, 2));
  168. ch.pb(Triangle(0, 1, 3));
  169. ch.pb(Triangle(0, 2, 3));
  170. ch.pb(Triangle(1, 2, 3));
  171.  
  172. for (int i = 4; i < n; i++)
  173. {
  174. add_point(i);
  175. }
  176.  
  177. cout.precision(6);
  178. cout << fixed;
  179.  
  180. int quest; scanf("%d", &quest);
  181. forn(i, quest)
  182. {
  183. Point q;
  184. scanf("%d %d %d", &q.x, &q.y, &q.z);
  185.  
  186. double ans = 1e+15;
  187. forv(j, ch)
  188. {
  189. ans = min(ans, dist(ch[j].s, q));
  190. }
  191. cout << ans << endl;
  192. }
  193. return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement