結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
/* -*- 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;}