結果
問題 | No.2376 障害物競プロ |
ユーザー |
|
提出日時 | 2023-07-07 21:57:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 594 ms / 4,000 ms |
コード長 | 2,828 bytes |
コンパイル時間 | 2,120 ms |
コンパイル使用メモリ | 199,060 KB |
最終ジャッジ日時 | 2025-02-15 07:16:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;using pii=pair<int,int>;#define all(a) a.begin(),a.end()#define pb push_back#define sz(a) ((int)a.size())const int N=305,mod=998244353;int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}int mul(int x, int y){return ((ll)x)*y%mod;}int Pow(int x, ll y=mod-2){int res=1; for(; y; x=mul(x,x),y>>=1) if(y&1) res=mul(res,x); return res;}const double eps = 1e-8, pi = acos(-1);int sign(double x) {return abs(x) <= eps ? 0 : (x > 0 ? 1 : -1);}struct Pt{ll x,y;constexpr Pt(ll _x=0, ll _y=0):x(_x),y(_y){}Pt operator + (Pt o) {return Pt(x + o.x, y + o.y);}Pt operator - (Pt o) {return Pt(x - o.x, y - o.y);}Pt operator * (ll k) {return Pt(x * k, y * k);}Pt operator / (ll k) {return Pt (x / k, y / k);}ll operator * (Pt o) {return x * o.x + y * o.y;}ll operator ^ (Pt o) {return x * o.y - y * o.x;}};struct Line {Pt a, b;};int ori(Pt o, Pt a, Pt b) {return sign((o - a) ^ (o - b));}bool btw(Pt a, Pt b, Pt c) { // c on segment ab?return ori(a, b, c) == 0 && sign((c - a) * (c - b)) <= 0;}bool SegsInter(Line a, Line b) {if (btw(a.a, a.b, b.a)) return 1;if (btw(a.a, a.b, b.b)) return 1;if (btw(b.a, b.b, a.a)) return 1;if (btw(b.a, b.b, a.b)) return 1;if (ori(a.a, a.b, b.a) * ori(a.a, a.b, b.b) == -1 && ori(b.a, b.b, a.a) * ori(b.a, b.b, a.b) == -1) return 1;return 0;}int n,m;double dis[N][N];Line a[N];bool good(Line l, int x, int y){for(int i=0; i<n; ++i) if(i!=x&&i!=y&&SegsInter(l,a[i])) return 0;return 1;}signed main(){ios_base::sync_with_stdio(0),cin.tie(0);cout << fixed << setprecision(20);cin >> n >> m;for(int i=0; i<n; ++i) cin >> a[i].a.x >> a[i].a.y >> a[i].b.x >> a[i].b.y;for(int i=0; i<n*2; ++i) for(int j=0; j<n*2; ++j) dis[i][j]=i==j?0:1e49;for(int i=0; i<n; ++i){bool ok=1;for(int j=0; j<n; ++j) if(i!=j&&SegsInter(a[i],a[j])) ok=0;if(ok) dis[i*2][i*2+1]=dis[i*2+1][i*2]=sqrt((a[i].b-a[i].a)*(a[i].b-a[i].a));}for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(i!=j){Pt de1[2]={a[i].a,a[i].b};Pt de2[2]={a[j].a,a[j].b};for(int ii: {0,1}) for(int jj: {0,1}) if(good({de1[ii],de2[jj]},i,j)) dis[i*2+ii][j*2+jj]=dis[j*2+jj][i*2+ii]=sqrt((de2[jj]-de1[ii])*(de2[jj]-de1[ii]));}//for(int i=0; i<n*2; ++i) for(int j=0; j<n*2; ++j) if(dis[i][j]<1e25) cout << i << ' ' << j << ' ' << dis[i][j] << endl;for(int k=0; k<n*2; ++k) for(int i=0; i<n*2; ++i) for(int j=0; j<n*2; ++j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);while(m--){int a1,b1,a2,b2; cin >> a1 >> b1 >> a2 >> b2; a1--,b1--,a2--,b2--;cout << dis[a1*2+b1][a2*2+b2] << "\n";}}