点と線（double を用いる）

//扱える値は int 値のみ
//できるだけ整数で計算し不可能なら double にするのが吉

// ２点のユークリッド距離を返す
double dist(int x1, int y1, int x2, int y2){
  return sqrt((double)(x2 - x1) * (x2 - x1) + (double)(y2 - y1) * (y2 - y1));
}

// ２点のマンハッタン距離を返す
double mdist(int x1, int y1, int x2, int y2){
  return abs(x2 - x1) + abs(y2 - y1);
}

// 外積
//線分ABと線分CDの交差を調べる時
//ACD BCD の符号が逆、CAB DAB の符号が逆であれば良い
int f(int ax, int ay, int bx, int by, int cx, int cy){
  int x1 = (bx-ax);
  int y1 = (by-ay);
  int x2 = (cx-ax);
  int y2 = (cy-ay);

  return x1 * y2 - y1 * x2;
}

// ２点を通る直線 ax + by + c = 0 の a, b, c を求める。
void abc(int x1, int y1, int x2, int y2, int &a, int &b, long long &c){
  a = y2 - y1;
  b = x1 - x2;
  c = (long long)x2 * y1 - (long long)x1 * y2;
}

// 点と直線 ax + by + c = 0 の距離を求める。
// 距離を比較するだけなら割り算せず long long 値を比較したほうが良い。
double distpl(int x, int y, int a, int b, long long c){
  if(a == 0 && b == 0)return -1.0;
  long long n = llabs((long long)a * x + (long long)b * y + c);
  return (double)n / sqrt(a * a + b * b);
}

// ２直線 a1x + b1y + c1 = 0 と a2x + b2y + c2 = 0 の交点
void crossll(double &ax, double &ay, int a1, int b1, long long c1, int a2, int b2, long long c2){
  double a[2][2], b[2], ret[2], w, m, s;
  
  if(a1 == 0 && b1 == 0)return;
  if(a2 == 0 && b2 == 0)return;
  if(a1 == 0 || b2 == 0){
    swap(a1, a2);
    swap(b1, b2);
    swap(c1, c2);
  }

  a[0][0]=a1; a[0][1]=b1; b[0]=-c1;
  a[1][0]=a2; a[1][1]=b2; b[1]=-c2;

  w = 1.0 / a[0][0];
  m = a[1][0] * w;
  a[1][1] -= m * a[0][1];
  b[1] -= m * b[0];

  ret[1] = b[1] / a[1][1];
  s = a[0][1] * ret[1];
  ret[0] = (b[0] - s) / a[0][0];
  
  ax = ret[0];
  ay = ret[1];
}