Guest User

sledding.cpp

a guest
May 6th, 2018
347
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define FR(i,a,b) for (int i=(a); i<(b); i++)
  3. #define F(i,n) FR(i,0,n)
  4. using namespace std;
  5. const int INF = 1e9, T=3;
  6. typedef long double ld;
  7.  
  8. struct p3 {ld x,y,z;};
  9. p3 operator+(p3 a, p3 b) {return {a.x+b.x, a.y+b.y, a.z+b.z};}
  10. p3 operator-(p3 a, p3 b) {return {a.x-b.x, a.y-b.y, a.z-b.z};}
  11. p3 operator*(p3 a, ld d) {return {a.x*d, a.y*d, a.z*d};}
  12. p3 operator/(p3 a, ld d) {return a*(1/d);}
  13. bool operator<(p3 a, p3 b) {return tie(a.x, a.y, a.z) < tie(b.x, b.y, b.z);}
  14. istream& operator>>(istream& is, p3 &p) {
  15.     return is>>p.x>>p.y>>p.z;}
  16. ostream& operator<<(ostream& os, p3 p) {
  17.     return os<<"("<<p.x<<","<<p.y<<","<<p.z<<")";}
  18. p3 operator*(p3 a, p3 b) {
  19.     return {a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x};
  20. }
  21. ld operator|(p3 a, p3 b) {return a.x*b.x + a.y*b.y + a.z*b.z;}
  22. ld abs(p3 a) {return sqrt(a|a);}
  23.  
  24. struct edge {int v,lo,hi;};
  25. struct uh {int u,h;};
  26. bool operator<(uh a, uh b) {return a.h < b.h;};
  27.  
  28. p3 planeInter(p3 a, p3 b, int h) {
  29.     return (a*(b.z-h) - b*(a.z-h))/(b.z-a.z);
  30. }
  31.  
  32. vector<p3> polygonUnder(vector<p3> ps, int h) {
  33.     vector<p3> under;
  34.     for (int i=0, n=ps.size(); i<n; i++) {
  35.         p3 a = ps[i], b = ps[(i+1)%n];
  36.        
  37.         // Keep points under h
  38.         if (a.z <= h)
  39.             under.push_back(a);
  40.        
  41.         // Add intersections
  42.         if ((a.z-h)*(b.z-h) < 0) // if a and b on either side
  43.             under.push_back(planeInter(a,b,h));
  44.     }
  45.     return under;
  46. }
  47.  
  48. signed main() {
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.     int n; cin>>n;
  52.     map<pair<p3,p3>, int> fromEdge;
  53.     vector<vector<p3>> ps(n, vector<p3>(T));
  54.     vector<vector<edge>> g(n);
  55.     F(i,n) {
  56.         F(j,T) cin>>ps[i][j];
  57.         F(j,T) {
  58.             p3 a = ps[i][j], b = ps[i][(j+1)%T];
  59.             if (fromEdge.count({a,b})) {
  60.                 int k = fromEdge[{a,b}];
  61.                 int lo = min(a.z, b.z), hi = max(a.z, b.z);
  62.                 g[i].push_back({k,lo,hi});
  63.                 g[k].push_back({i,lo,hi});
  64.             } else {
  65.                 fromEdge[{b,a}] = i;
  66.             }
  67.         }
  68.     }
  69.     vector<int> h(n, -INF);
  70.     h[0] = ps[0][0].z;
  71.     priority_queue<uh> pq;
  72.     pq.push({0,h[0]});
  73.     while (!pq.empty()) {
  74.         uh cur = pq.top(); pq.pop();
  75.         int u = cur.u;
  76.         if (cur.h < h[u])
  77.             continue;
  78.         for (edge e : g[u]) if (h[u] >= e.lo) {
  79.             int newH = min(h[u], e.hi);
  80.             if (h[e.v] < newH) {
  81.                 h[e.v] = newH;
  82.                 pq.push({e.v, newH});
  83.             }
  84.         }
  85.     }
  86.     ld tot = 0;
  87.     F(i,n) {
  88.         vector<p3> under = polygonUnder(ps[i], h[i]);
  89.         p3 sum{0,0,0};
  90.         int m = under.size();
  91.         F(j,m)
  92.             sum = sum + under[j]*under[(j+1)%m];
  93.         tot += abs(sum)/2;
  94.     }
  95.     cout<<fixed<<setprecision(12)<<tot<<"\n";
  96. }
RAW Paste Data