第十七届浙大城市学院程序设计竞赛 J Sumo and Balloon

Sumo and Balloon

https://ac.nowcoder.com/acm/contest/5954/J

J Sumo and Balloon

题目地址：

https://ac.nowcoder.com/acm/contest/5954/J

基本思路：

计算几何，难点主要是确定嘴到墙面的距离是多少，也就是要算一个点到平面的距离。这个其实我们根据高中的几何知识就能求解了(我直接套板子了不愿推了，大家可以推一下OWO)。然后这个距离其实就是球的最大直径，知道了这个接下来根据球的体积公式 $V = 4/3 \pi*r^{3}$ 就能直接运算了，我这里想多了还写了个二分，二分了吹气的秒数，大家不要学。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const double eps = 1e-8, inf = 1e8, pi = acos(-1);

int sgn(double x) {
  if (x > eps)
    return 1;
  if (x < -eps)
    return -1;
  return 0;
}

struct point3 {
    double x, y, z;

    point3() {}

    point3(double _x, double _y, double _z) {
      x = _x;
      y = _y;
      z = _z;
    }

    point3 operator-(const point3 &p) const {
      return point3(x - p.x, y - p.y, z - p.z);
    }

    point3 operator+(const point3 &p) const {
      return point3(x + p.x, y + p.y, z - p.z);
    }

    point3 operator*(const point3 &p) const {
      return point3(y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x);
    }

    double operator/(const point3 &p) const {
      return x * p.x + y * p.y + z * p.z;
    }
};

void get_panel(const point3 &p1, const point3 &p2, const point3 &p3,
               double &A, double &B, double &C, double &D) {
  A = ((p2.y - p1.y) * (p3.z - p1.z) - (p2.z - p1.z) * (p3.y - p1.y));
  B = ((p2.z - p1.z) * (p3.x - p1.x) - (p2.x - p1.x) * (p3.z - p1.z));
  C = ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x));
  D = (-(A * p1.x + B * p1.y + C * p1.z));
}

double dist_panel(const point3 &pt, double A, double B, double C, double D) {
  return abs(A * pt.x + B * pt.y + C * pt.z + D) /
         sqrt(A * A + B * B + C * C);
}

double L,k;
bool check(double s) {
  double v = s * L;
  double r = pow((3.0 * v) / (4.0 * pi), 1.0 / 3.0);
  double R = 2 * r;
  return sgn(R - k) <= 0;
}

signed main() {
  IO;
  cin >> L;
  point3 pt, p[3];
  cin >> pt.x >> pt.y >> pt.z;
  for (int i = 0; i < 3; i++) cin >> p[i].x >> p[i].y >> p[i].z;
  double A, B, C, D;
  get_panel(p[0], p[1], p[2], A, B, C, D);
  k = dist_panel(pt, A, B, C, D);
  double l = 0,r = INF;
  for(int i = 0 ; i <= 1000000 ; i++){
    double mid = (l + r) / 2.0;
    if(check(mid)) l = mid;
    else r = mid;
  }
  printf("%.10lf\n",l);
  return 0;
}