Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:64000000")
- #define _CRT_SECURE_NO_DEPRECATE
- #include <cmath>
- #include <cassert>
- #include <cstdio>
- #include <ctime>
- #include <iostream>
- #include <sstream>
- #include <map>
- #include <set>
- #include <vector>
- #include <string>
- #include <queue>
- #include <deque>
- #include <algorithm>
- #include <stack>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define all(v) v.begin(), v.end()
- #define forn(i, n) for (int i = 0; i < (int)(n); i++)
- #define for1(i, n) for (int i = 1; i <= (int)(n); i++)
- #define forv(i, v) forn(i, v.size())
- typedef pair<int, int> pii;
- typedef long long ll;
- #define NMAX 1005
- struct Point
- {
- int x, y, z;
- };
- Point center;
- int used[NMAX][NMAX];
- ll det(ll x1, ll y1, ll x2, ll y2)
- {
- return x1 * y2 - x2 * y1;
- }
- struct Plane
- {
- ll a, b, c, d;
- Plane() {};
- Plane(Point& p1, Point& p2, Point& p3)
- {
- a = det(p1.y - p2.y, p3.y - p1.y, p1.z - p2.z, p3.z - p1.z);
- b = det(p1.z - p2.z, p3.z - p1.z, p1.x - p2.x, p3.x - p1.x);
- c = det(p1.x - p2.x, p3.x - p1.x, p1.y - p2.y, p3.y - p1.y);
- d = -(a * p1.x + b * p1.y + c * p1.z);
- if (a * center.x + b * center.y + c * center.z + 4 * d < 0)
- {
- a = -a;
- b = -b;
- c = -c;
- d = -d;
- }
- }
- };
- Point p[NMAX];
- struct Triangle
- {
- vector<int> v;
- Plane s;
- Triangle() {};
- Triangle(int i, int j, int k)
- {
- v.pb(i);
- v.pb(j);
- v.pb(k);
- forv(i1, v)
- {
- forv(i2, v)
- {
- if (v[i1] < v[i2]) used[v[i1]][v[i2]]++;
- }
- }
- s = Plane(p[i], p[j], p[k]);
- }
- };
- vector<Triangle> ch;
- int n;
- bool inside(Plane& s, Point& p)
- {
- return s.a * p.x + s.b * p.y + s.c * p.z + s.d > 0;
- }
- void add_point(int id)
- {
- vector<bool> deleted(ch.size(), false);
- vector<pii> edges;
- forv(i, ch)
- {
- if (!inside(ch[i].s, p[id]))
- {
- deleted[i] = true;
- forv(j, ch[i].v)
- {
- forv(k, ch[i].v)
- {
- if (ch[i].v[j] < ch[i].v[k])
- {
- used[ch[i].v[j]][ch[i].v[k]]--;
- edges.pb(mp(ch[i].v[j], ch[i].v[k]));
- }
- }
- }
- }
- }
- int k = 0;
- forv(i, ch)
- {
- if (!deleted[i])
- {
- ch[k++] = ch[i];
- }
- }
- ch.resize(k);
- forv(i, edges)
- {
- if (used[edges[i].first][edges[i].second] == 1)
- {
- ch.pb(Triangle(id, edges[i].first, edges[i].second));
- }
- }
- }
- double dist(Plane& s, Point& p)
- {
- 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));
- }
- int main()
- {
- freopen("worm.in", "rt", stdin);
- freopen("worm.out", "wt", stdout);
- scanf("%d", &n);
- forn(i, n)
- {
- scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
- }
- forn(i, 4)
- {
- center.x += p[i].x;
- center.y += p[i].y;
- center.z += p[i].z;
- }
- ch.pb(Triangle(0, 1, 2));
- ch.pb(Triangle(0, 1, 3));
- ch.pb(Triangle(0, 2, 3));
- ch.pb(Triangle(1, 2, 3));
- for (int i = 4; i < n; i++)
- {
- add_point(i);
- }
- cout.precision(6);
- cout << fixed;
- int quest; scanf("%d", &quest);
- forn(i, quest)
- {
- Point q;
- scanf("%d %d %d", &q.x, &q.y, &q.z);
- double ans = 1e+15;
- forv(j, ch)
- {
- ans = min(ans, dist(ch[j].s, q));
- }
- cout << ans << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement