結果

問題 No.2376 障害物競プロ
ユーザー tnakao0123tnakao0123
提出日時 2024-06-26 09:49:26
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 361 ms / 4,000 ms
コード長 2,693 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 60,356 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 09:50:19
合計ジャッジ時間 52,663 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2376.cc:  No.2376 髫懷ｮｳ迚ｩ遶ｶ繝励Ο - yukicoder
 */

#include<cstdio>
#include<cmath>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_N = 150;
const int MAX_GN = MAX_N * 2;
const double DINF = 1e60;

/* typedef */

typedef long long ll;

template <typename T>
struct Pt {
  T x, y;
  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &p) : x(p.x), y(p.y) {}

  Pt<T> operator+(const Pt<T> p) const { return Pt<T>(x + p.x, y + p.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> p) const { return Pt<T>(x - p.x, y - p.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }
  Pt<T> mid(const Pt<T> p) { return Pt<T>((x + p.x) / 2, (y + p.y) / 2); }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  Pt<T> rot(double th) {
    double c = cos(th), s = sin(th);
    return Pt<T>(c * x - s * y, s * x + c * y);
  }

  Pt<T> rot90() { return Pt<T>(-y, x); }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  void print() { printf("(%d,%d)", x, y); }
};

using pt = Pt<int>;

/* global variables */

pt ps[MAX_GN];
double ds[MAX_GN][MAX_GN];

/* subroutines */

bool cross_segs(const pt& a0, const pt& a1, const pt& b0, const pt& b1) {
  pt va(a1 - a0), vb(b1 - b0);
  return
    (ll)va.cross(b0 - a0) * va.cross(b1 - a0) < 0 &&
    (ll)vb.cross(a0 - b0) * vb.cross(a1 - b0) < 0;
}

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  int gn = 0;
  for (int i = 0; i < n; i++) {
    int x0, y0, x1, y1;
    scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
    ps[gn++] = pt(x0, y0), ps[gn++] = pt(x1, y1);
  }

  for (int i = 0; i < gn; i++) {
    ds[i][i] = 0.0;
    for (int j = i + 1; j < gn; j++) {
      ds[i][j] = ds[j][i] = DINF;
      int ei = i >> 1, ej = j >> 1;
      if (ei != ej) {
	bool ok = true;
	for (int k = 0; ok && k < n; k++)
	  if (k != ei && k != ej)
	    ok = ! cross_segs(ps[i], ps[j], ps[k * 2], ps[k * 2 + 1]);
	if (ok)
	  ds[i][j] = ds[j][i] = (ps[j] - ps[i]).d();
      }
    }
  }

  for (int k = 0; k < gn; k++)
    for (int i = 0; i < gn; i++)
      for (int j = 0; j < gn; j++)
	ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);

  while (m--) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    a--, b--, c--, d--;

    int i = a * 2 + b, j = c * 2 + d;
    printf("%.10lf\n", ds[i][j]);
  }
  return 0;
}
0