not's memo

ICPC2013国内予選E

16:22 |

３つのロープを決めてそれがピンと張る点を求めるのが難しいだけですが、実は直線の交点求めるだけでOKです。

まず、２つのロープabがピンと張る領域はz=0の平面に垂直な円になります。

３つのロープabcについて考えるとabについての円とacについての円の交点になります。

これを上から見てz=0の平面に射影してやると直線の交点になっています。

#include<iostream>
#include<complex>
#include<cstdio>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define X real()
#define Y imag()

typedef long double D;
typedef complex<D> P;
struct L{P a, b;};

const D EPS = 1e-8;

D det(P a, P b) {return a.X * b.Y - a.Y * b.X;}
P vec(L a) {return a.b - a.a;} 

// 直線の交点
P pLL(L a, L b) {return a.a + vec(a) * (det(vec(b), b.a - a.a) / det(vec(b), vec(a)));}

int n;
P pp[11];
D l[11], res;

// ２点を決めてロープがピンと張る点
P b(int i, int j) {return pp[i] + (pp[j] - pp[i]) * (norm(pp[i] - pp[j]) + l[i] * l[i] - l[j] * l[j]) / (2 * norm(pp[i] - pp[j]));}

// 点を決めた時にどれだけ高くできるか求めてresを更新
void h(P p) {
  D r = 1e9;
  rep (i, n) r = min(r, sqrt(max(l[i] * l[i] - norm(pp[i] - p), (D)0)));
  res = max(res, r);
}

int main() {
  while (cin >> n, n) {
    rep (i, n) cin >> pp[i].X >> pp[i].Y >> l[i];
    res = 0;
    // １点
    rep (i, n) h(pp[i]);
    // ２点
    rep (i, n) rep (j, i) h(b(i, j));
    // ３点
    rep (i, n) rep (j, i) rep (k, j) if (abs(det(pp[j] - pp[i], pp[k] - pp[i])) > EPS) {
      P b1 = b(i, j), b2 = b(i, k);
      h(pLL((L){b1, b1 + (pp[i] - pp[j]) * P(0, 1)}, (L){b2, b2 + (pp[i] - pp[k]) * P(0, 1)}));
    }
    printf("%.12Lf\n", res);
  }
  return 0;
}

ツイートする