Advertisement
Um_nik

Untitled

Apr 26th, 2022
864
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <ctime>
  13. #include <cassert>
  14. #include <complex>
  15. #include <string>
  16. #include <cstring>
  17. #include <chrono>
  18. #include <random>
  19. #include <bitset>
  20. #include <array>
  21. using namespace std;
  22.  
  23. #ifdef LOCAL
  24.     #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
  25. #else
  26.     #define eprintf(...) 42
  27. #endif
  28.  
  29. using ll = long long;
  30. using ld = long double;
  31. using uint = unsigned int;
  32. using ull = unsigned long long;
  33. template<typename T>
  34. using pair2 = pair<T, T>;
  35. using pii = pair<int, int>;
  36. using pli = pair<ll, int>;
  37. using pll = pair<ll, ll>;
  38. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  39. ll myRand(ll B) {
  40.     return (ull)rng() % B;
  41. }
  42.  
  43. #define pb push_back
  44. #define mp make_pair
  45. #define all(x) (x).begin(),(x).end()
  46. #define fi first
  47. #define se second
  48.  
  49. clock_t startTime;
  50. double getCurrentTime() {
  51.     return (double)(clock() - startTime) / CLOCKS_PER_SEC;
  52. }
  53.  
  54. struct Point {
  55.     ll x, y;
  56.  
  57.     Point() : x(), y() {}
  58.     Point(ll _x, ll _y) : x(_x), y(_y) {}
  59.  
  60.     Point operator - (const Point &a) const {
  61.         return Point(x - a.x, y - a.y);
  62.     }
  63.     ll operator * (const Point &a) const {
  64.         return x * a.y - y * a.x;
  65.     }
  66.     int getQ() const {
  67.         if (x == 0) {
  68.             return (y > 0 ? 0 : 1);
  69.         }
  70.         return (x > 0 ? 0 : 1);
  71.     }
  72.     bool operator < (const Point &a) const {
  73.         int q1 = getQ(), q2 = a.getQ();
  74.         if (q1 != q2) return q1 < q2;
  75.         return *this * a > 0;
  76.     }
  77. };
  78.  
  79. const int N = 300300;
  80. int n, m, k;
  81. int ed[N][4];
  82. Point pts[N];
  83. int z[N];
  84. vector<pair<Point, int>> g[N];
  85. vector<bool> usedEd[N];
  86. vector<int> faces[N];
  87. vector<int> facesForEdge[N];
  88. double ANS[N];
  89.  
  90. double sqr(double x) {
  91.     return x * x;
  92. }
  93.  
  94. struct Quad {
  95.     double A, B, C;
  96.  
  97.     Quad() : A(), B(), C() {}
  98.     Quad(double _A, double _B, double _C) : A(_A), B(_B), C(_C) {}
  99.  
  100.     double eval(double x) {
  101.         return A * x * x + B * x + C;
  102.     }
  103.  
  104.     Quad operator + (const Quad &Q) const {
  105.         return Quad(A + Q.A, B + Q.B, C + Q.C);
  106.     }
  107.     Quad operator - (const Quad &Q) const {
  108.         return Quad(A - Q.A, B - Q.B, C - Q.C);
  109.     }
  110.     Quad operator * (const double &k) const {
  111.         return Quad(A * k, B * k, C * k);
  112.     }
  113.    
  114.     bool operator < (const Quad &Q) const {
  115.         return false;
  116.     }
  117. };
  118. struct Area {
  119.     Quad S;
  120.     multiset<pair<int, Quad>> setik;
  121.  
  122.     Area() : S(), setik() {}
  123.  
  124.     double eval(double x) {
  125.         while(!setik.empty() && -setik.begin()->first > x) {
  126.             S = S + setik.begin()->second;
  127.             setik.erase(setik.begin());
  128.         }
  129.         return S.eval(x);
  130.     }
  131. };
  132. int par[N];
  133. int sz[N];
  134. Area area[N];
  135.  
  136. int getPar(int v) {
  137.     return (par[v] == v ? v : par[v] = getPar(par[v]));
  138. }
  139. void unite(int v, int u) {
  140.     v = getPar(v);
  141.     u = getPar(u);
  142.     if (v == u) return;
  143.     if (sz[v] < sz[u]) swap(v, u);
  144.     sz[v] += sz[u];
  145.     par[u] = v;
  146.     area[v].S = area[v].S + area[u].S;
  147.     for (auto t : area[u].setik) area[v].setik.insert(t);
  148. }
  149.  
  150. struct Event {
  151.     int t;
  152.     int x;
  153.     int v, u;
  154.  
  155.     Event() : t(), x(), v(), u() {}
  156.     Event(int _t, int _x, int _v, int _u) : t(_t), x(_x), v(_v), u(_u) {}
  157.  
  158.     bool operator < (const Event &e) const {
  159.         if (x != e.x) return x > e.x;
  160.         return t > e.t;
  161.     }
  162. };
  163. vector<Event> events;
  164.  
  165. void read() {
  166.     scanf("%d%d", &n, &m);
  167.     for (int i = 0; i < n; i++) {
  168.         scanf("%lld%lld%d", &pts[i].x, &pts[i].y, &z[i]);
  169.     }
  170.     for (int i = 0; i < m; i++) {
  171.         int v, u;
  172.         scanf("%d%d", &v, &u);
  173.         v--;u--;
  174.         ed[i][0] = v;
  175.         ed[i][1] = u;
  176.         g[v].push_back(mp(pts[u] - pts[v], i));
  177.         g[u].push_back(mp(pts[v] - pts[u], i));
  178.     }
  179.     for (int v = 0; v < n; v++) {
  180.         sort(all(g[v]));
  181.         for (int i = 0; i < (int)g[v].size(); i++) {
  182.             int id = g[v][i].second;
  183.             if (ed[id][0] == v)
  184.                 ed[id][2] = i;
  185.             else
  186.                 ed[id][3] = i;
  187.         }
  188.         usedEd[v] = vector<bool>(g[v].size(), false);
  189.     }
  190.     for (int v = 0; v < n; v++)
  191.         for (int i = 0; i < (int)g[v].size(); i++) if (!usedEd[v][i]) {
  192.             int u = v;
  193.             int p = i;
  194.             ll S = 0;
  195.             vector<int> edges;
  196.             while(!usedEd[u][p]) {
  197.                 usedEd[u][p] = 1;
  198.                 int id = g[u][p].second;
  199.                 int w = ed[id][0] ^ ed[id][1] ^ u;
  200.                 int q = ed[id][2] ^ ed[id][3] ^ p;
  201.                 S += pts[u] * pts[w];
  202.                 edges.push_back(id);
  203.                 if (q == 0) q = (int)g[w].size();
  204.                 q--;
  205.                 u = w;
  206.                 p = q;
  207.             }
  208.             if (S < 0) continue;
  209.             assert((int)edges.size() == 3);
  210.             faces[k++] = edges;
  211.         }
  212.     eprintf("faces:\n");
  213.     for (int i = 0; i < k; i++) {
  214.         for (int id : faces[i])
  215.             eprintf("%d ", id);
  216.         eprintf("\n");
  217.     }
  218.     for (int i = 0; i < k; i++)
  219.         for (int id : faces[i])
  220.             facesForEdge[id].push_back(i);
  221.     for (int i = 0; i < m; i++) {
  222.         if ((int)facesForEdge[i].size() < 2) continue;
  223.         assert((int)facesForEdge[i].size() == 2);
  224.         int v = facesForEdge[i][0], u = facesForEdge[i][1];
  225.         events.push_back(Event(0, max(z[ed[i][0]], z[ed[i][1]]), v, u));
  226.     }
  227.     scanf("%d", &m);
  228.     for (int i = 0; i < m; i++) {
  229.         int h, v;
  230.         scanf("%d%d", &h, &v);
  231.         v--;
  232.         if (h >= z[v]) {
  233.             ANS[i] = -1;
  234.             continue;
  235.         }
  236.         v = g[v][0].second;
  237.         v = facesForEdge[v][0];
  238.         events.push_back(Event(1, h, v, i));
  239.     }
  240.     sort(all(events));
  241. }
  242.  
  243. double getPlanarArea(vector<int> vert) {
  244.     int v = vert[0], u = vert[1], w = vert[2];
  245.     double x1 = pts[u].x - pts[v].x;
  246.     double y1 = pts[u].y - pts[v].y;
  247.     double z1 = z[u] - z[v];
  248.     double x2 = pts[w].x - pts[v].x;
  249.     double y2 = pts[w].y - pts[v].y;
  250.     double z2 = z[w] - z[v];
  251.     double x3 = y1 * z2 - z1 * y2;
  252.     double y3 = z1 * x2 - x1 * z2;
  253.     double z3 = x1 * y2 - y1 * x2;
  254.     double S = sqrt(x3 * x3 + y3 * y3 + z3 * z3);
  255.     return S / 2;
  256. }
  257. Area getArea(vector<int> vert) {
  258.     Area A = Area();
  259.     int z0 = z[vert[0]], z1 = z[vert[1]], z2 = z[vert[2]];
  260.     if (z0 > z1) swap(z0, z1);
  261.     if (z1 > z2) swap(z1, z2);
  262.     if (z0 > z1) swap(z0, z1);
  263.     vector<Quad> sss(4, Quad());
  264.     double S = getPlanarArea(vert);
  265.     if (z0 == z2) {
  266.         A.setik.insert(mp(-z0, Quad(0, 0, S)));
  267.         return A;
  268.     }
  269. //  eprintf("full area %.5lf\n", S);
  270.     sss[0] = Quad(0, 0, S);
  271.     double Smid = S * (z2 - z1) / (z2 - z0);
  272.     if (z1 == z2) {
  273.         sss[2] = sss[3];
  274.     } else {
  275.         double SS = Smid / sqr(z2 - z1);
  276.         sss[2] = Quad(1, -2 * z2, (double)z2 * z2) * SS;
  277.     }
  278.     if (z0 == z1) {
  279.         sss[1] = sss[0];
  280.     } else {
  281.         double SS = (S - Smid) / sqr(z1 - z0);
  282.         sss[1] = Quad(1, -2 * z0, (double)z0 * z0) * SS;
  283.         sss[1] = sss[0] - sss[1];
  284.     }
  285.     vector<int> zz = {z0, z1, z2};
  286.     for (int i = 0; i < 3; i++)
  287.         A.setik.insert(mp(-zz[i], sss[i] - sss[i + 1]));
  288.     return A;
  289. }
  290.  
  291. int main()
  292. {
  293.     startTime = clock();
  294. //  freopen("input.txt", "r", stdin);
  295. //  freopen("output.txt", "w", stdout);
  296.  
  297.     read();
  298.     for (int i = 0; i < k; i++) {
  299.         vector<int> vert;
  300.         for (int id : faces[i]) {
  301.             vert.push_back(ed[id][0]);
  302.             vert.push_back(ed[id][1]);
  303.         }
  304.         sort(all(vert));
  305.         vert.resize(unique(all(vert)) - vert.begin());
  306.         assert((int)vert.size() == 3);
  307.         area[i] = getArea(vert);
  308.         par[i] = i;
  309.         sz[i] = 1;
  310.     }
  311.     for (Event e : events) {
  312.         if (e.t == 0) {
  313.             unite(e.v, e.u);
  314.         } else {
  315.             ANS[e.u] = area[getPar(e.v)].eval(e.x);
  316.         }
  317.     }
  318.     for (int i = 0; i < m; i++) {
  319.         if (ANS[i] > -0.5)
  320.             printf("%.14lf\n", ANS[i]);
  321.         else
  322.             printf("-1\n");
  323.     }
  324.  
  325.     return 0;
  326. }
  327.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement