結果

問題 No.2376 障害物競プロ
ユーザー i_am_noobi_am_noob
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0