結果

問題 No.2376 障害物競プロ
ユーザー milanis48663220milanis48663220
提出日時 2023-07-07 23:02:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 734 ms / 4,000 ms
コード長 6,592 bytes
コンパイル時間 1,693 ms
コンパイル使用メモリ 128,448 KB
実行使用メモリ 5,252 KB
最終ジャッジ日時 2023-09-29 00:41:06
合計ジャッジ時間 62,833 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 380 ms
4,376 KB
testcase_05 AC 535 ms
4,380 KB
testcase_06 AC 224 ms
4,380 KB
testcase_07 AC 727 ms
5,216 KB
testcase_08 AC 734 ms
5,160 KB
testcase_09 AC 715 ms
5,156 KB
testcase_10 AC 709 ms
5,148 KB
testcase_11 AC 662 ms
5,152 KB
testcase_12 AC 642 ms
5,220 KB
testcase_13 AC 690 ms
4,892 KB
testcase_14 AC 717 ms
5,140 KB
testcase_15 AC 662 ms
4,848 KB
testcase_16 AC 716 ms
5,216 KB
testcase_17 AC 645 ms
5,116 KB
testcase_18 AC 638 ms
5,212 KB
testcase_19 AC 652 ms
5,096 KB
testcase_20 AC 663 ms
5,096 KB
testcase_21 AC 660 ms
5,104 KB
testcase_22 AC 555 ms
4,388 KB
testcase_23 AC 396 ms
5,000 KB
testcase_24 AC 400 ms
4,384 KB
testcase_25 AC 189 ms
4,380 KB
testcase_26 AC 457 ms
4,388 KB
testcase_27 AC 370 ms
4,384 KB
testcase_28 AC 237 ms
4,384 KB
testcase_29 AC 188 ms
4,384 KB
testcase_30 AC 252 ms
4,844 KB
testcase_31 AC 235 ms
4,384 KB
testcase_32 AC 31 ms
4,384 KB
testcase_33 AC 103 ms
4,380 KB
testcase_34 AC 123 ms
4,380 KB
testcase_35 AC 76 ms
4,380 KB
testcase_36 AC 441 ms
5,252 KB
testcase_37 AC 499 ms
4,384 KB
testcase_38 AC 182 ms
4,384 KB
testcase_39 AC 564 ms
5,196 KB
testcase_40 AC 214 ms
4,956 KB
testcase_41 AC 171 ms
4,384 KB
testcase_42 AC 709 ms
5,220 KB
testcase_43 AC 698 ms
5,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cmath>
#include <numeric>
#include <functional>
#include <cassert>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
typedef long long ll;

template<typename T>
vector<vector<T>> vec2d(int n, int m, T v){
    return vector<vector<T>>(n, vector<T>(m, v));
}

template<typename T>
vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));
}

template<typename T>
void print_vector(vector<T> v, char delimiter=' '){
    if(v.empty()) {
        cout << endl;
        return;
    }
    for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;
    cout << v.back() << endl;
}

template<typename T>
struct line {
    line(T a, T b, T c): a(a), b(b), c(c){};
    T a, b, c;
};

template<typename T>
ostream& operator<<(ostream& os, const line<T>& l){
    os << l.a << "*x + " << l.b << "*y+ " << l.c;
    return os;
}

template<typename T>
inline T add(T a, T b){
    return a+b;
}

const double eps = 1e-10;

inline double add(double a, double b){
    if(abs(a+b) < eps*(abs(a)+abs(b))) return 0.0;
    return a+b;
}

template<typename T>
class point {
    public:
    point<T>(T x, T y): x(x), y(y){};
    point<T>(): x(0), y(0){};
    T x, y;
    point<T> operator + (point<T> p){
        return point<T>(add(x, p.x), add(y, p.y));
    };
    point<T> operator - (point<T> p){
        return point<T>(add(x, -p.x), add(y, -p.y));
    };
    point<T> operator * (T d){
        return point<T>(x*d, y*d);
    };
    T dot(point<T> p){
        return add(x*p.x, y*p.y);
    };
    T det(point<T> p){
        return add(x*p.y, -y*p.x);
    };
};

/**
 * 直線lとp1, p2を結ぶ直線を求めます
 */ 
template<typename T>
line<T> from_points(point<T> p1, point<T> p2){
    return line(p2.y-p1.y, p1.x-p2.x, p1.y*p2.x-p1.x*p2.y);
}

/**
 * l: ax+by+c = 0としたときにax+by+cの値を返します
 */ 
template<typename T>
T substitute(line<T> l, point<T> p){
    return p.x*l.a+p.y*l.b+l.c;
}

/**
 * 直線lとp1, p2を結ぶ線分が交点を持つか否かを返します
 */ 
template<typename T>
bool intersect(line<T> l, point<T> p1, point<T> p2){
    return (substitute(l, p1) > 0) ^ (substitute(l, p2) > 0);
}

/**
 * p1, p2を結ぶ線分とq1, q2を結ぶ線分が交点を持つか否かを返します
 */ 
template<typename T>
bool intersect(point<T> p1, point<T> p2, point<T> q1, point<T> q2){
    auto lp = from_points(p1, p2);
    auto lq = from_points(q1, q2);
    bool fq = (substitute(lq, p1) > 0) ^ (substitute(lq, p2) > 0);
    bool fp = (substitute(lp, q1) > 0) ^ (substitute(lp, q2) > 0);
    return fp&&fq;
}

template<typename T>
double dist(point<T> p1, point<T> p2){
    T dx = p1.x-p2.x;
    T dy = p1.y-p2.y;
    return sqrt(dx*dx+dy*dy);
}

template<typename T>
T dist_sq(point<T> p1, point<T> p2){
    T dx = p1.x-p2.x;
    T dy = p1.y-p2.y;
    return dx*dx+dy*dy;
}

/**
 * 線分p1p2の垂直二等分線を求めます
 */ 
line<double> vertical_bisector(point<double> p1, point<double> p2){
    double a = 2.0*(p2.x-p1.x);
    double b = 2.0*(p2.y-p1.y);
    double c = p2.x*p2.x-p1.x*p1.x+p2.y*p2.y-p1.y*p1.y;
    return line<double>(a, b, -c);
}

/**
 * 直線l1と直線l2がただ一つの交点を持つかを返します
 */ 
bool intersect(line<double> l1, line<double> l2){
    if(abs(l1.a*l2.b-l2.a*l1.b) < eps) return false;
    return true;
}

/**
 * 直線l1と直線l2の交点を求めます
 * 戻り値をoptionalに書き換えるほうが良さそう
 */ 
point<double> intersection(line<double> l1, line<double> l2){
    assert(intersect(l1, l2));
    double x = l1.b*l2.c-l2.b*l1.c;
    double y = l2.a*l1.c-l1.a*l2.c;
    double d = l1.a*l2.b-l2.a*l1.b;
    return point<double>(x/d, y/d);
}

point<double> rot(double theta, point<double> p){
    double x = p.x;
    double y = p.y;
    double c = cos(theta);
    double s = sin(theta);
    return point<double>(c*x-s*y, c*y+s*x);
}

const double INF = 1e+15;

vector<vector<double>> warshallfloyd(vector<vector<double>> g){
    int n = g.size();
    vector<vector<double>> dist(n, vector<double>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            dist[i][j] = g[i][j];
        }
        dist[i][i] = 0;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                double new_len = dist[j][i] + dist[i][k];
                dist[j][k] = min(new_len, dist[j][k]);
            }
        }
    }
    return dist;
}

using Po = point<int>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n, m; cin >> n >> m;
    vector<vector<Po>> points;
    for(int i = 0; i < n; i++){
        points.push_back({});
        for(int j = 0; j < 2; j++){
            int x, y; cin >> x >> y;
            points.back().push_back(Po(x, y));
        }
    }
    auto to_idx = [&](int i, int j){
        return i*2+j;
    };
    auto g = vec2d(n*2, n*2, INF);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < n; k++){
                for(int l = 0; l < 2; l++){
                    if(i == k) continue;
                    bool ok = true;
                    for(int p = 0; p < n; p++){
                        if(p == i || p == k) continue;
                        if(intersect(points[i][j], points[k][l], points[p][0], points[p][1])) ok = false;
                    }
                    if(ok){
                        int idx0 = to_idx(i, j);
                        int idx1 = to_idx(k, l);
                        g[idx0][idx1] = dist(points[i][j], points[k][l]);
                        // cout << i << ' ' << j << "->" << k << ' ' << l << ':' << g[idx0][idx1] << endl;
                    }
                }
            }
        }
    }
    auto dist = warshallfloyd(g);

    for(int i = 0; i < m; i++){
        int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; d--;
        int i0 = to_idx(a, b);
        int i1 = to_idx(c, d);
        cout << dist[i0][i1] << endl;
    }
}
0