点と線分の距離 ～long double VER～

ライブラリ 
// #define EPS (1e-14)
#define EPS (1e-12)
#define equals(a,b) (fabs((a)-(b)) < EPS)

code (library)

typedef complex<ld> C;

// 2点を与えると ax + by = c なる(a,b,c)を返します
VI get_a_b_c_from_two_points(C p, C q){
  ll x1=p.real();
  ll y1=p.imag();
  ll x2=q.real();
  ll y2=q.imag();
  ll a = y1-y2;
  ll b = x2-x1;
  ll c = y1*(x2-x1)-x1*(y2-y1);
  return {a,b,c};
}

// 外積
ld cross(C a, C b){
  return a.real()*b.imag() - a.imag()*b.real();
}

// 内積
ld dot(C a, C b){
  return a.real() * b.real() + a.imag() * b.imag();
}

// ベクトルの長さ
ld length(C v){
  return sqrt(v.real()*v.real() + v.imag()*v.imag());
}

// 2点間の距離
ld distance_between_two_points(C a, C b){
  return length(a-b);
}

// 単位ベクトル
C unit_vector(C v){
  return v / length(v);
}

// 点pを点a,bからなる直線に射影した点を返す
C point_projection_to_line(C p, C a, C b){
  C v = b-a;
  C u = unit_vector(v);
  C AP = p - a;
  // APをuに射影
  ld len = dot(AP, u);
  return a + u*len;
}

// 2点がほぼ同じ位置か
bool is_same_position(C a, C b){
  ld d = distance_between_two_points(a,b);
  if(equals(d,0))return true;
  return false;
}

// 2つのベクトルが平行か
bool is_parallel(C v, C w){
  ld area = cross(v,w);
  if(equals(area,0))return true;
  return false;
}

// 点pが線分a,bの間にいるか（接するのも含む）
bool is_in_segment(C p, C a, C b){
  if(is_same_position(p,a))return true;
  if(is_same_position(p,b))return true;
  // 平行でないならありえない
  auto pa = a-p;
  auto pb = b-p;
  if(!is_parallel(pa,pb))return false;
  // 以降、平行
  if(dot(pa,pb)<0)return true;
  return false;
}

// 点pと線分a,bの距離
ld distance_point_to_segment(C p, C a, C b){
  ld mi = inf;
  chmin(mi, distance_between_two_points(p,a));
  chmin(mi, distance_between_two_points(p,b));
  C q = point_projection_to_line(p,a,b);
  if(is_in_segment(q,a,b)){
    chmin(mi, distance_between_two_points(p,q));
  }
  return mi;
}

// 線分が交差するか
// ベクトル p0->p1, q0->q1
// https://perogram.hateblo.jp/entry/is_intersect
bool is_intersect(C p0, C p1, C q0, C q1){

  {
    // 同じ点があるなら交差
    if(p0==p1)return true;
    if(p0==q0)return true;
    if(p0==q1)return true;
    if(p1==q0)return true;
    if(p1==q1)return true;
    if(q0==q1)return true;
  }

  bool is_parallel = false;
  {
    C v = p0-p1;
    C w = q0-q1;
    if(cross(v,w)==0) is_parallel=true;
  }

  if(is_parallel){
    // 包含・重なり・ギリギリ接触を交差とする
    if(is_in_segment(p0,q0,q1))return true;
    if(is_in_segment(p1,q0,q1))return true;
    if(is_in_segment(q0,p0,p1))return true;
    if(is_in_segment(q1,p0,p1))return true;
    return false;
  }

  // 以降、平行ではないとする

  // p側から見た交差チェック
  auto v0 = p1 - p0;
  auto v1 = q0 - p0;
  auto v2 = q1 - p0;
  if(cross(v0, v1) * cross(v0, v2) > 0){
      return false;
  }
  // q側から見た交差チェック
  v0 = q1 - q0;
  v1 = p0 - q0;
  v2 = p1 - q0;
  if(cross(v0, v1) * cross(v0, v2) > 0){
      return false;
  }
  return true;
}

他人のライブラリ

verify