結果
問題 | No.2376 障害物競プロ |
ユーザー | 259-Momone |
提出日時 | 2024-03-19 21:48:19 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,159 ms / 4,000 ms |
コード長 | 2,452 bytes |
コンパイル時間 | 5,886 ms |
コンパイル使用メモリ | 329,380 KB |
実行使用メモリ | 6,676 KB |
最終ジャッジ日時 | 2024-03-19 21:49:39 |
合計ジャッジ時間 | 75,171 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 3 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 489 ms
6,548 KB |
testcase_05 | AC | 723 ms
6,676 KB |
testcase_06 | AC | 309 ms
6,676 KB |
testcase_07 | AC | 1,058 ms
6,676 KB |
testcase_08 | AC | 1,088 ms
6,676 KB |
testcase_09 | AC | 1,072 ms
6,676 KB |
testcase_10 | AC | 1,067 ms
6,676 KB |
testcase_11 | AC | 1,004 ms
6,676 KB |
testcase_12 | AC | 979 ms
6,676 KB |
testcase_13 | AC | 993 ms
6,676 KB |
testcase_14 | AC | 1,066 ms
6,676 KB |
testcase_15 | AC | 952 ms
6,676 KB |
testcase_16 | AC | 1,050 ms
6,676 KB |
testcase_17 | AC | 971 ms
6,676 KB |
testcase_18 | AC | 960 ms
6,676 KB |
testcase_19 | AC | 1,136 ms
6,676 KB |
testcase_20 | AC | 1,122 ms
6,676 KB |
testcase_21 | AC | 1,117 ms
6,676 KB |
testcase_22 | AC | 776 ms
6,676 KB |
testcase_23 | AC | 597 ms
6,676 KB |
testcase_24 | AC | 502 ms
6,676 KB |
testcase_25 | AC | 237 ms
6,676 KB |
testcase_26 | AC | 571 ms
6,676 KB |
testcase_27 | AC | 476 ms
6,676 KB |
testcase_28 | AC | 336 ms
6,676 KB |
testcase_29 | AC | 241 ms
6,676 KB |
testcase_30 | AC | 411 ms
6,676 KB |
testcase_31 | AC | 325 ms
6,676 KB |
testcase_32 | AC | 45 ms
6,676 KB |
testcase_33 | AC | 165 ms
6,676 KB |
testcase_34 | AC | 176 ms
6,676 KB |
testcase_35 | AC | 96 ms
6,676 KB |
testcase_36 | AC | 667 ms
6,676 KB |
testcase_37 | AC | 688 ms
6,676 KB |
testcase_38 | AC | 245 ms
6,676 KB |
testcase_39 | AC | 861 ms
6,676 KB |
testcase_40 | AC | 370 ms
6,676 KB |
testcase_41 | AC | 224 ms
6,676 KB |
testcase_42 | AC | 1,109 ms
6,676 KB |
testcase_43 | AC | 1,159 ms
6,676 KB |
ソースコード
#include <bits/extc++.h> template <class S, class T> std::ostream &operator<<(std::ostream &os, const std::pair<S, T> &p) { os << "[" << p.first << " " << p.second << "]"; return os; } int main() { using namespace std; unsigned N, M; cin >> N >> M; using point = pair<unsigned long, unsigned long>; vector<pair<point, point>> segments(N); for (auto &&[p1, p2] : segments) { auto &&[x1, y1]{p1}; auto &&[x2, y2]{p2}; long a, b, c, d; cin >> a >> b >> c >> d; x1 = a + 10000; y1 = b + 10000; x2 = c + 10000; y2 = d + 10000; } vector distances(2 * N, vector<long double>(2 * N, sqrt(numeric_limits<long double>::max()))); const auto side{[](const auto &p, const auto &segment) { const auto &[x, y]{p}; const auto &[p1, p2]{segment}; const auto &[x1, y1]{p1}; const auto &[x2, y2]{p2}; const auto positive_part{x1 * y2 + x2 * y + x * y1}; const auto negative_part{x2 * y1 + x * y2 + x1 * y}; return (positive_part > negative_part) - (positive_part < negative_part); }}; for (unsigned i{}; i < 2 * N; ++i) { const auto &p1{i & 1 ? segments[i / 2].second : segments[i / 2].first}; for (unsigned j{}; j < 2 * N; ++j) { const auto &p2{j & 1 ? segments[j / 2].second : segments[j / 2].first}; if (ranges::all_of(segments, [&side, &p1, &p2](const auto &s) { auto x{side(p1, s)}, y{side(p2, s)}; auto t{side(s.first, make_pair(p1, p2))}, u{side(s.second, make_pair(p1, p2))}; if (x * y + 1 == 0 && t * u + 1 == 0) return false; return true; })) distances[i][j] = hypot(static_cast<long double>(p1.first) - p2.first, static_cast<long double>(p1.second) - p2.second); } } for (unsigned _{}; _ < 3; ++_) for (unsigned k{}; k < 2 * N; ++k) for (unsigned i{}; i < 2 * N; ++i) for (unsigned j{}; j < 2 * N; ++j) distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j]); cout << fixed << setprecision(15); for (unsigned i{}, a, b, c, d; i < M; ++i) { cin >> a >> b >> c >> d; --a; --b; --c; --d; cout << distances[a * 2 + b][c * 2 + d] << endl; } return 0; }