結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-07 22:18:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 831 ms / 4,000 ms |
コード長 | 1,632 bytes |
コンパイル時間 | 1,955 ms |
コンパイル使用メモリ | 175,564 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-21 18:25:08 |
合計ジャッジ時間 | 70,976 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;const double INF = 1000000000;struct point{int x, y;point(){}point(int x, int y): x(x), y(y){}point operator -(point P){return point(x - P.x, y - P.y);}};double abs(point P){return hypot(P.x, P.y);}double dist(point P, point Q){return abs(Q - P);}int cross(point A, point B){return A.x * B.y - A.y * B.x;}int main(){cout << fixed << setprecision(20);int N, M;cin >> N >> M;vector<point> P(N * 2);for (int i = 0; i < N * 2; i++){cin >> P[i].x >> P[i].y;}vector<vector<double>> D(N * 2, vector<double>(N * 2, INF));for (int i = 0; i < N * 2; i++){for (int j = i + 1; j < N * 2; j++){bool ok = true;for (int k = 0; k < N; k++){long long a = cross(P[k * 2] - P[i], P[j] - P[i]);long long b = cross(P[k * 2 + 1] - P[i], P[j] - P[i]);if (a > 0 && b < 0 || a < 0 && b > 0){long long c = cross(P[i] - P[k * 2], P[k * 2 + 1] - P[k * 2]);long long d = cross(P[j] - P[k * 2], P[k * 2 + 1] - P[k * 2]);if (c > 0 && d < 0 || c < 0 && d > 0){ok = false;}}}if (ok){D[i][j] = dist(P[i], P[j]);D[j][i] = dist(P[i], P[j]);}}}for (int i = 0; i < N * 2; i++){for (int j = 0; j < N * 2; j++){for (int k = 0; k < N * 2; k++){D[j][k] = min(D[j][k], D[j][i] + D[i][k]);}}}for (int i = 0; i < M; i++){int a, b, c, d;cin >> a >> b >> c >> d;a--;b--;c--;d--;cout << D[a * 2 + b][c * 2 + d] << endl;}}