Algoogle

Algorithm for Programming Contest

直線と線分

基本情報


illとcllとそれに関するものだけverified

解説


直線クラス. 線分も兼ねている.

  • vec: 方向ベクトル
  • norm: ノルム
  • abs: 原点からの距離
  • proj: 正射影
  • refl: 線対称な点

各関数名は以下の規則に従っている.

  • 接頭辞(1文字, 動作)
    • i: 交差判定
    • c: 交点
    • d: 距離
  • 接尾辞(2文字, 引数)
    • l: 直線
    • s: 線分
    • p: 点

コード


(line.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
namespace D2 {
/*
  depends on
  point
*/
struct line {
    point a, b;
    line(){}
    line(point a, point b) : a(a), b(b) {}

    point vec() const { return b-a; }
    double abs() const { return vec().abs(); }
    double norm() const { return vec().norm(); }
    point proj(const point &p) const { return a+vec().proj(p-a); }
    point refl(const point &p) const { return proj(p)*2-p; }
};
std::ostream &operator<<(std::ostream &os, const line &l) { os << l.a << " - " << l.b; return os; }

bool ill(const line &l, const line &m) { return std::abs(l.vec().det(m.vec())) > eps; }
bool ils(const line &l, const line &s) { return ccw(l.a,l.b,s.a)*ccw(l.a,l.b,s.b)<=0; }
bool isl(const line &s, const line &l) { return ils(l,s); }
bool iss(const line &s, const line &t) { return ils(s,t) and ils(t,s); }
point cll(const line &l, const line &m) { return l.a+l.vec()*(m.vec().det(m.a-l.a)/m.vec().det(l.vec())); }
double dlp(const line &l, const point &p) { return (l.proj(p)-p).abs(); }
double dpl(const point &p, const line &l) { return dlp(l,p); }
double dll(const line &l, const line &m) { return ill(l,m) ? 0.0 : dlp(l,m.a); }
double dps(const point &p, const line &s) { return ccw(s.a,s.b,s.proj(p)) ? std::min((s.a-p).abs(), (s.b-p).abs()) : (s.proj(p)-p).abs(); }
double dsp(const line &s, const point &p) { return dps(p,s); }
double dss(const line &s, const line &m) { return iss(s,m)? 0.0 : std::min(std::min(dps(m.a,s),dps(m.b,s)), std::min(dps(s.a,m),dps(s.b,m))); }

}

Comments