Guest User

paint.cpp

a guest
May 6th, 2018
176
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. typedef long double ld;
  6.  
  7. typedef complex<ld> pt;
  8. ld cross(pt a, pt b) {return imag(conj(a)*b);}
  9.  
  10. // area of [x,oo) x [y,oo) inter C((0,0),r)
  11. ld quadCircle(ld r, ld x, ld y) {
  12.     assert(x >= 0 && y >= 0);
  13.     if (x*x+y*y >= r*r)
  14.         return 0;
  15.     pt p(x,y), a(sqrt(r*r-y*y), y), b(x, sqrt(r*r-x*x));
  16.     return (cross(p,a) + r*r*asin(min(cross(a,b)/r/r, 1.0L)) + cross(b,p))/2;
  17. }
  18.  
  19. // area of [x,x+1] x [y,y+1] inter C((0,0),r)
  20. ld squareCircle(ld r, ld x, ld y) {
  21.     return quadCircle(r,x,y) - quadCircle(r,x+1,y) - quadCircle(r,x,y+1) + quadCircle(r,x+1,y+1);
  22. }
  23.  
  24. struct p3 {int x,y,z;};
  25.  
  26. ld getRadius(ld d, ld ratio) {
  27.     ld alpha = acos(min(cbrt(d*d*ratio), 1.0L));
  28.     return d*tan(alpha);
  29. }
  30.  
  31. signed main() {
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(NULL);
  34.     int n,l; cin>>n>>l;
  35.     vector<p3> ps(n);
  36.     for (p3 &p : ps)
  37.         cin >> p.x >> p.y >> p.z;
  38.     ld lo = 0, hi = 1; // ratio 3D angle / paint used
  39.     for (;;) {
  40.         ld mid = (lo+hi)/2;
  41.         vector<ld> paintOn(n,0);
  42.         F(i,n) {
  43.             p3 p = ps[i];
  44.             auto paintFace = [&](int d, int x, int y) {
  45.                 if (d > 0)
  46.                     paintOn[i] += squareCircle(getRadius(d,mid), x, y);
  47.             };
  48.             paintFace(p.x, p.y, p.z);
  49.             paintFace(p.y, p.x, p.z);
  50.             paintFace(p.z, p.x, p.y);
  51.         }
  52.         if (mid == hi || mid == lo) {
  53.             cout << fixed << setprecision(8);
  54.             F(i,n) cout << paintOn[i] << "\n";
  55.             break;
  56.         } else {
  57.             ld sum = 0;
  58.             F(i,n) sum += paintOn[i];
  59.             if (sum < l)
  60.                 hi = mid;
  61.             else
  62.                 lo = mid;
  63.         }
  64.     }
  65. }
RAW Paste Data