Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <queue>
- #include <ctime>
- #include <cassert>
- #include <complex>
- #include <string>
- #include <cstring>
- #include <chrono>
- #include <random>
- #include <bitset>
- #include <array>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
- #else
- #define eprintf(...) 42
- #endif
- using ll = long long;
- using ld = long double;
- using uint = unsigned int;
- using ull = unsigned long long;
- template<typename T>
- using pair2 = pair<T, T>;
- using pii = pair<int, int>;
- using pli = pair<ll, int>;
- using pll = pair<ll, ll>;
- mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
- ll myRand(ll B) {
- return (ull)rng() % B;
- }
- #define pb push_back
- #define mp make_pair
- #define all(x) (x).begin(),(x).end()
- #define fi first
- #define se second
- clock_t startTime;
- double getCurrentTime() {
- return (double)(clock() - startTime) / CLOCKS_PER_SEC;
- }
- struct Point {
- ll x, y;
- Point() : x(), y() {}
- Point(ll _x, ll _y) : x(_x), y(_y) {}
- Point operator - (const Point &a) const {
- return Point(x - a.x, y - a.y);
- }
- ll operator * (const Point &a) const {
- return x * a.y - y * a.x;
- }
- int getQ() const {
- if (x == 0) {
- return (y > 0 ? 0 : 1);
- }
- return (x > 0 ? 0 : 1);
- }
- bool operator < (const Point &a) const {
- int q1 = getQ(), q2 = a.getQ();
- if (q1 != q2) return q1 < q2;
- return *this * a > 0;
- }
- };
- const int N = 300300;
- int n, m, k;
- int ed[N][4];
- Point pts[N];
- int z[N];
- vector<pair<Point, int>> g[N];
- vector<bool> usedEd[N];
- vector<int> faces[N];
- vector<int> facesForEdge[N];
- double ANS[N];
- double sqr(double x) {
- return x * x;
- }
- struct Quad {
- double A, B, C;
- Quad() : A(), B(), C() {}
- Quad(double _A, double _B, double _C) : A(_A), B(_B), C(_C) {}
- double eval(double x) {
- return A * x * x + B * x + C;
- }
- Quad operator + (const Quad &Q) const {
- return Quad(A + Q.A, B + Q.B, C + Q.C);
- }
- Quad operator - (const Quad &Q) const {
- return Quad(A - Q.A, B - Q.B, C - Q.C);
- }
- Quad operator * (const double &k) const {
- return Quad(A * k, B * k, C * k);
- }
- bool operator < (const Quad &Q) const {
- return false;
- }
- };
- struct Area {
- Quad S;
- multiset<pair<int, Quad>> setik;
- Area() : S(), setik() {}
- double eval(double x) {
- while(!setik.empty() && -setik.begin()->first > x) {
- S = S + setik.begin()->second;
- setik.erase(setik.begin());
- }
- return S.eval(x);
- }
- };
- int par[N];
- int sz[N];
- Area area[N];
- int getPar(int v) {
- return (par[v] == v ? v : par[v] = getPar(par[v]));
- }
- void unite(int v, int u) {
- v = getPar(v);
- u = getPar(u);
- if (v == u) return;
- if (sz[v] < sz[u]) swap(v, u);
- sz[v] += sz[u];
- par[u] = v;
- area[v].S = area[v].S + area[u].S;
- for (auto t : area[u].setik) area[v].setik.insert(t);
- }
- struct Event {
- int t;
- int x;
- int v, u;
- Event() : t(), x(), v(), u() {}
- Event(int _t, int _x, int _v, int _u) : t(_t), x(_x), v(_v), u(_u) {}
- bool operator < (const Event &e) const {
- if (x != e.x) return x > e.x;
- return t > e.t;
- }
- };
- vector<Event> events;
- void read() {
- scanf("%d%d", &n, &m);
- for (int i = 0; i < n; i++) {
- scanf("%lld%lld%d", &pts[i].x, &pts[i].y, &z[i]);
- }
- for (int i = 0; i < m; i++) {
- int v, u;
- scanf("%d%d", &v, &u);
- v--;u--;
- ed[i][0] = v;
- ed[i][1] = u;
- g[v].push_back(mp(pts[u] - pts[v], i));
- g[u].push_back(mp(pts[v] - pts[u], i));
- }
- for (int v = 0; v < n; v++) {
- sort(all(g[v]));
- for (int i = 0; i < (int)g[v].size(); i++) {
- int id = g[v][i].second;
- if (ed[id][0] == v)
- ed[id][2] = i;
- else
- ed[id][3] = i;
- }
- usedEd[v] = vector<bool>(g[v].size(), false);
- }
- for (int v = 0; v < n; v++)
- for (int i = 0; i < (int)g[v].size(); i++) if (!usedEd[v][i]) {
- int u = v;
- int p = i;
- ll S = 0;
- vector<int> edges;
- while(!usedEd[u][p]) {
- usedEd[u][p] = 1;
- int id = g[u][p].second;
- int w = ed[id][0] ^ ed[id][1] ^ u;
- int q = ed[id][2] ^ ed[id][3] ^ p;
- S += pts[u] * pts[w];
- edges.push_back(id);
- if (q == 0) q = (int)g[w].size();
- q--;
- u = w;
- p = q;
- }
- if (S < 0) continue;
- assert((int)edges.size() == 3);
- faces[k++] = edges;
- }
- eprintf("faces:\n");
- for (int i = 0; i < k; i++) {
- for (int id : faces[i])
- eprintf("%d ", id);
- eprintf("\n");
- }
- for (int i = 0; i < k; i++)
- for (int id : faces[i])
- facesForEdge[id].push_back(i);
- for (int i = 0; i < m; i++) {
- if ((int)facesForEdge[i].size() < 2) continue;
- assert((int)facesForEdge[i].size() == 2);
- int v = facesForEdge[i][0], u = facesForEdge[i][1];
- events.push_back(Event(0, max(z[ed[i][0]], z[ed[i][1]]), v, u));
- }
- scanf("%d", &m);
- for (int i = 0; i < m; i++) {
- int h, v;
- scanf("%d%d", &h, &v);
- v--;
- if (h >= z[v]) {
- ANS[i] = -1;
- continue;
- }
- v = g[v][0].second;
- v = facesForEdge[v][0];
- events.push_back(Event(1, h, v, i));
- }
- sort(all(events));
- }
- double getPlanarArea(vector<int> vert) {
- int v = vert[0], u = vert[1], w = vert[2];
- double x1 = pts[u].x - pts[v].x;
- double y1 = pts[u].y - pts[v].y;
- double z1 = z[u] - z[v];
- double x2 = pts[w].x - pts[v].x;
- double y2 = pts[w].y - pts[v].y;
- double z2 = z[w] - z[v];
- double x3 = y1 * z2 - z1 * y2;
- double y3 = z1 * x2 - x1 * z2;
- double z3 = x1 * y2 - y1 * x2;
- double S = sqrt(x3 * x3 + y3 * y3 + z3 * z3);
- return S / 2;
- }
- Area getArea(vector<int> vert) {
- Area A = Area();
- int z0 = z[vert[0]], z1 = z[vert[1]], z2 = z[vert[2]];
- if (z0 > z1) swap(z0, z1);
- if (z1 > z2) swap(z1, z2);
- if (z0 > z1) swap(z0, z1);
- vector<Quad> sss(4, Quad());
- double S = getPlanarArea(vert);
- if (z0 == z2) {
- A.setik.insert(mp(-z0, Quad(0, 0, S)));
- return A;
- }
- // eprintf("full area %.5lf\n", S);
- sss[0] = Quad(0, 0, S);
- double Smid = S * (z2 - z1) / (z2 - z0);
- if (z1 == z2) {
- sss[2] = sss[3];
- } else {
- double SS = Smid / sqr(z2 - z1);
- sss[2] = Quad(1, -2 * z2, (double)z2 * z2) * SS;
- }
- if (z0 == z1) {
- sss[1] = sss[0];
- } else {
- double SS = (S - Smid) / sqr(z1 - z0);
- sss[1] = Quad(1, -2 * z0, (double)z0 * z0) * SS;
- sss[1] = sss[0] - sss[1];
- }
- vector<int> zz = {z0, z1, z2};
- for (int i = 0; i < 3; i++)
- A.setik.insert(mp(-zz[i], sss[i] - sss[i + 1]));
- return A;
- }
- int main()
- {
- startTime = clock();
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- read();
- for (int i = 0; i < k; i++) {
- vector<int> vert;
- for (int id : faces[i]) {
- vert.push_back(ed[id][0]);
- vert.push_back(ed[id][1]);
- }
- sort(all(vert));
- vert.resize(unique(all(vert)) - vert.begin());
- assert((int)vert.size() == 3);
- area[i] = getArea(vert);
- par[i] = i;
- sz[i] = 1;
- }
- for (Event e : events) {
- if (e.t == 0) {
- unite(e.v, e.u);
- } else {
- ANS[e.u] = area[getPar(e.v)].eval(e.x);
- }
- }
- for (int i = 0; i < m; i++) {
- if (ANS[i] > -0.5)
- printf("%.14lf\n", ANS[i]);
- else
- printf("-1\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement