結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-06-19 20:40:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 501 ms / 4,000 ms |
コード長 | 3,075 bytes |
コンパイル時間 | 2,064 ms |
コンパイル使用メモリ | 204,100 KB |
最終ジャッジ日時 | 2025-02-14 23:06:53 |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;struct Point {ll x, y;Point(ll x = 0, ll y = 0) : x(x), y(y) {}Point& operator+=(const Point& v) noexcept {x += v.x;y += v.y;return *this;}Point& operator-=(const Point& v) noexcept {x -= v.x;y -= v.y;return *this;}Point operator+(const Point& v) const noexcept { return Point(*this) += v; }Point operator-(const Point& v) const noexcept { return Point(*this) -= v; }};ll norm(const Point& a) { return a.x * a.x + a.y * a.y; }ll dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }ll cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }int ccw(const Point& p0, const Point& p1, const Point& p2) {Point a = p1 - p0;Point b = p2 - p0;if (cross(a, b) > 0) { return 1; }if (cross(a, b) < 0) { return -1; }if (dot(a, b) < 0) { return 2; }if (norm(a) < norm(b)) { return -2; }return 0;}bool is_intersected(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) &&(ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);}bool on_segment(const Point& p1, const Point& p2, const Point& p) {return ccw(p1, p2, p) == 0;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);int N, M;cin >> N >> M;vector<vector<int>> x(N, vector<int>(2));vector<vector<int>> y(N, vector<int>(2));for (int i = 0; i < N; i++) {cin >> x[i][0] >> y[i][0] >> x[i][1] >> y[i][1];}int N2 = N * 2;int inf = (1 << 30);vector<vector<double>> G(N2, vector<double>(N2, inf));for (int i = 0; i < N2; i++) {G[i][i] = 0;int a = i / 2;int b = i % 2;int x1 = x[a][b];int y1 = y[a][b];Point p1(x1, y1);for (int j = i + 1; j < N2; j++) {int c = j / 2;int d = j % 2;int x2 = x[c][d];int y2 = y[c][d];Point p2(x2, y2);bool ok = [&]() -> bool {for (int k = 0; k < N; k++) {if (k == a || k == c) { continue; }Point p3(x[k][0], y[k][0]);Point p4(x[k][1], y[k][1]);if (is_intersected(p1, p2, p3, p4)) { return false; }}return true;}();if (ok) { G[i][j] = G[j][i] = hypot(x2 - x1, y2 - y1); }}}for (int k = 0; k < N2; k++) {for (int i = 0; i < N2; i++) {for (int j = 0; j < N2; j++) {G[i][j] = min(G[i][j], G[i][k] + G[k][j]);}}}for (int i = 0; i < M; i++) {int a, b, c, d;cin >> a >> b >> c >> d;a--;b--;c--;d--;int s = 2 * a + b;int t = 2 * c + d;double ans = G[s][t];cout << ans << '\n';}return 0;}