保存されている過去のバージョンの一覧

2015年01月29日00時10分45秒

yukicoder No.132 - 点と平面との距離（writer担当）

Source

ニコニコミュニティ
問題文

問題概要

$3$ 次元上の $N+1$ 点 $P,Q_1,Q_2,\ldots,Q_N$ が与えられる．
点 $Q_i,Q_j,Q_k$ が通る平面と，点 $P$ の距離を ${\rm dist}(i,j,k)$ とした時に，
$\quad \displaystyle \sum_{1 \leq i < j < k \leq N} {\rm dist}(i,j,k)$
の値を求める問題．

解法

$i,j,k$ の組み合わせは全部試せば良く，平面と点の距離を $O(1)$ で求められれば良い．
まず，$P$ が現任になるように平行移動しておくと楽なのでしておく．
四面体 $P,Q_i,Q_j,Q_k$ に対して，底面を $Q_i,Q_j,Q_k$ と思った時のこの四面体の高さが求めるべき距離．
例えば，体積は行列式を用いて，底面の三角形の面積は三辺の長さからヘロンの公式で求めることができるので，高さは逆算で求まる．
時間計算量は $O(N^3)$ で，重いのは距離を求める（sqrt）ところなので，距離は全ての点と点の間の距離を最初に求めておけば，距離を求める回数は $O(N^2)$ になる．
他にも，各平面に対して法線ベクトルを外積で求めれば，$ax+by+cz+d=0$ という形の平面の式を求められるので，（直線と点の距離の公式に似たような形の）平面と点との距離の公式を用いても良い．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N;
double X[501], Y[501], Z[501];
double dist[501][501];

int main(){
  int i, a, b, c;
  double dx, dy, dz;
  double d1, d2, d3, ss, s, v;
  double res;

  scanf("%d",&N);
  scanf("%lf%lf%lf",&dx,&dy,&dz);
  rep(i,N) scanf("%lf%lf%lf",X+i,Y+i,Z+i), X[i]-=dx, Y[i]-=dy, Z[i]-=dz;

  rep(a,N) REP(b,a+1,N) dist[a][b] = dist[b][a] = sqrt( (X[a]-X[b])*(X[a]-X[b]) + (Y[a]-Y[b])*(Y[a]-Y[b]) + (Z[a]-Z[b])*(Z[a]-Z[b]) );

  res = 0;
  rep(a,N) REP(b,a+1,N) REP(c,b+1,N){
    d1 = dist[a][b];
    d2 = dist[b][c];
    d3 = dist[c][a];
    ss = (d1+d2+d3) / 2;
    s = sqrt(ss*(ss-d1)*(ss-d2)*(ss-d3));

    v = (X[a]*Y[b]*Z[c] + X[b]*Y[c]*Z[a] + X[c]*Y[a]*Z[b] - X[c]*Y[b]*Z[a] - X[b]*Y[a]*Z[c] - X[a]*Y[c]*Z[b]) / 2;
    res += max(v, -v) / s;
  }
  printf("%.15f\n", res);
  
  return 0;
}

Current time: 2024年04月25日15時37分52秒
Last modified: 2015年01月29日00時10分45秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：