結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-10 19:11:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 735 ms / 4,000 ms |
コード長 | 1,442 bytes |
コンパイル時間 | 4,202 ms |
コンパイル使用メモリ | 255,948 KB |
最終ジャッジ日時 | 2025-02-15 09:35:57 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001int main(){int n,m;cin>>n>>m;vector<long long> x(n*2),y(n*2);//,z(n),w(n);rep(i,n*2){cin>>x[i]>>y[i];}vector d(n*2,vector<double>(n*2,1e18));rep(i,n*2){rep(j,n*2){if(i==j)d[i][j] = 0.0;bool f = false;if(i%2==0 && i+1==j)f = true;else{f = true;rep(k,n){if(k==i/2 || k==j/2)continue;long long t = 1;long long dx0 = x[j]-x[i],dy0 = y[j]-y[i];long long dx1 = x[k*2]-x[j], dy1 = y[k*2]-y[j];t *= dx0*dy1 - dx1*dy0;dx1 = x[k*2+1]-x[j], dy1 = y[k*2+1]-y[j];t *= dx0*dy1 - dx1*dy0;if(t<0){dx0 = x[k*2]-x[k*2+1],dy0 = y[k*2]-y[k*2+1];dx1 = x[k*2+1]-x[i], dy1 = y[k*2+1]-y[i];t = 1;t *= dx0*dy1 - dx1*dy0;dx1 = x[k*2+1]-x[j], dy1 = y[k*2+1]-y[j];t *= dx0*dy1 - dx1*dy0;if(t<0){f = false;break;}}}if(f){d[i][j] = hypot(x[j]-x[i],y[j]-y[i]);}}}}rep(i,n*2){rep(j,n*2){rep(k,n*2){d[j][k] = min(d[j][k],d[j][i] + d[i][k]);}}}rep(_,m){int a,b,c,D;cin>>a>>b>>c>>D;a--,b--,c--,D--;cout<<fixed<<setprecision(10)<<d[a*2 + b][c*2 + D]<<endl;}return 0;}