not's memo

１次元幾何ライブラリ

10:53 |

#include<algorithm>
#include<complex>
#include<cstdio>
#include<iostream>
#include<queue>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

typedef long double D;
typedef D P;
typedef pair<D, D> L;
typedef vector<P> Pol;

const D INF = 1e100;
const D EPS = 1e-8;
const D PI = acos(-1);

template<class T> bool eq(T a, T b) {return abs(a - b) < EPS;}
template<class T> int sig(T r) {return eq(r, 0) ? 0 : r > 0 ? 1 : -1;}

// 内積
D dot(P a, P b) {return a * b;}
// 外積
D det(P a, P b) {return 0;}

// 線分のベクトル
P vec(L a) {return a.second - a.first;}

// 線分abに対する点xの位置
enum CCW{FRONT = 1, BACK = 2, ON = 4};
int ccw(L s, P p) {
  if (sig(s.first - p) * sig(p - s.second) >= 0) return ON;
  return (sig(s.first - s.second) == sig(s.second - p)) ? FRONT : BACK;
}

// 有向角度
D arg(P base, P a, P b) {return ccw(L(base, a), b) == BACK ? PI : 0;}

// 射影
P proj(P a, P b) {return b;}
P perp(L l, P p) {return p;}
P refl(L l, P p) {return p;}

// 交差判定
bool iLL(L a, L b) {return true;}
bool iLS(L a, L b) {return true;}
bool iSS(L a, L b) {
  int cwa = ccw(a, b.first) | ccw(a, b.second);
  int cwb = ccw(b, a.first) | ccw(b, a.second);
  return (cwa | cwb) & ON;
}

// 距離
D dLP(L l, P x) {return 0;}
D dSP(L s, P x) {return ccw(s, x) == ON ? 0 : min(abs(s.first - x), abs(s.second - x));}
D dLL(L a, L b) {return 0;}
D dLS(L a, L b) {return 0;}
D dSS(L a, L b) {return min(min(dSP(a, b.first), dSP(a, b.second)), min(dSP(b, a.first), dSP(b, a.second)));}

// 多角形の面積
D aPol(Pol vp) {return 0;}

// 三角形の面積
D aTri(D a, D b, D c) {return 0;}

// 多角形の内外判定 内部:1、周上:0、外部:-1
int sGP(Pol pol, P p) {
  return sig(*min_element(pol.begin(), pol.end()) - p) * sig(p - *max_element(pol.begin(), pol.end()));
}

// 凸包
Pol convexHull(Pol p) {
  Pol pol;
  pol.push_back(*min_element(p.begin(), p.end()));
  pol.push_back(*max_element(p.begin(), p.end()));
  return pol;
}

// 線分をマージする
vector<L> merge(vector<L> s) {
  rep (i, s.size()) if (s[i].second < s[i].first) swap(s[i].first, s[i].second);
  sort(s.begin(), s.end());
  rep (i, s.size()) rep (j, i) if (iSS(s[i], s[j])) {
    s[j].second = max(s[i].second, s[j].second);
    s.erase(s.begin() + i--);
    break;
  }
  return s;
}

ツイートする