結果

問題 No.2376 障害物競プロ
ユーザー i_am_noobi_am_noob
提出日時 2023-07-07 21:57:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 605 ms / 4,000 ms
コード長 2,828 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 202,360 KB
実行使用メモリ 4,436 KB
最終ジャッジ日時 2023-09-28 23:10:38
合計ジャッジ時間 68,702 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 261 ms
4,376 KB
testcase_05 AC 366 ms
4,380 KB
testcase_06 AC 150 ms
4,376 KB
testcase_07 AC 430 ms
4,380 KB
testcase_08 AC 428 ms
4,384 KB
testcase_09 AC 414 ms
4,384 KB
testcase_10 AC 416 ms
4,436 KB
testcase_11 AC 331 ms
4,424 KB
testcase_12 AC 299 ms
4,384 KB
testcase_13 AC 420 ms
4,384 KB
testcase_14 AC 419 ms
4,416 KB
testcase_15 AC 394 ms
4,384 KB
testcase_16 AC 413 ms
4,384 KB
testcase_17 AC 313 ms
4,412 KB
testcase_18 AC 294 ms
4,388 KB
testcase_19 AC 570 ms
4,408 KB
testcase_20 AC 581 ms
4,388 KB
testcase_21 AC 578 ms
4,428 KB
testcase_22 AC 352 ms
4,384 KB
testcase_23 AC 229 ms
4,388 KB
testcase_24 AC 270 ms
4,380 KB
testcase_25 AC 129 ms
4,380 KB
testcase_26 AC 305 ms
4,384 KB
testcase_27 AC 260 ms
4,380 KB
testcase_28 AC 144 ms
4,380 KB
testcase_29 AC 131 ms
4,380 KB
testcase_30 AC 120 ms
4,380 KB
testcase_31 AC 153 ms
4,384 KB
testcase_32 AC 20 ms
4,388 KB
testcase_33 AC 57 ms
4,388 KB
testcase_34 AC 78 ms
4,384 KB
testcase_35 AC 53 ms
4,384 KB
testcase_36 AC 242 ms
4,388 KB
testcase_37 AC 334 ms
4,388 KB
testcase_38 AC 122 ms
4,388 KB
testcase_39 AC 320 ms
4,384 KB
testcase_40 AC 85 ms
4,388 KB
testcase_41 AC 121 ms
4,388 KB
testcase_42 AC 597 ms
4,384 KB
testcase_43 AC 605 ms
4,388 KB
権限があれば一括ダウンロードができます

ソースコード

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