Div1 1000 ConstructPolyline

問題

3次元空間で(0, 0, 0)と(x_i, y_i, z_i)を結ぶ線分が与えられ，その線分を（回転させたり曲げたりするの禁止）繋ぎ合わせて途中で交わらない折れ線を作る．
その折れ線の両端が最も離れるように繋げたときの両端の距離の２乗を求めよ．

考え方

とりあえず特定の方向について伸ばすことにしよう．で，その「特定の方向」を充分な数分散させて計算すれば網羅できるはず．

その方向について，１度もバックすることがないようにすればどの順に繋いでも折れ線が途中で交わることはない．で，繋げる順番は最終的な結果に影響を及ぼさない．
なので線分が「目的の方向」を向いていれば(0,0,0)の方を，逆方向を向いていれば(x,y,z)の方を接続すると目的の方向に伸びることになる．目的の方向を向いているかどうかは内積で判断しましょう．

コード

#include <vector>
#include <cmath>
using namespace std;

class ConstructPolyline
{
  long long sqLength(vector<int>& vx, vector<int>& vy, vector<int>& vz, double dx, double dy, double dz)
  {
    int x = 0, y = 0, z = 0;
    for( int i = 0 ; i < vx.size() ; ++i ) {
      int sgn = 1;
      if( vx[i]*dx + vy[i]*dy + vz[i]*dz < 0 ) sgn = -1;
      x += vx[i] * sgn;
      y += vy[i] * sgn;
      z += vz[i] * sgn;
    }
    return (long long)x * x + (long long)y * y + (long long)z * z;
  }
public:
  long long maximizeLength(vector<int> x, vector<int> y, vector<int> z)
  {
    const int N = 200;
    double dt = 2 * M_PI / N;
    long long max = 0;
    for( int i = 0 ; i < N ; ++i ) {
      double th = dt * i;
      double dx = cos(th);
      double dr = sin(th);
      for( int j = -N / 2 ; j < N / 2 ; ++j ) {
        double phi = dt * j;
        double dy = dr * cos(phi);
        double dz = dr * sin(phi);
        long long length = sqLength(x, y, z, dx, dy, dz); 
        if( length > max ) max = length;
      }
    }
    return max;
  }
};