#888730 (C++17) No.2376 障害物競プロ

提出ソース

結果

問題	No.2376 障害物競プロ
ユーザー	siganai
提出日時	2023-07-07 22:39:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	15,486 bytes
コンパイル時間	2,847 ms
コンパイル使用メモリ	223,396 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-21 18:54:37
合計ジャッジ時間	52,371 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	208 ms 5,376 KB
testcase_05	AC	295 ms 5,376 KB
testcase_06	AC	129 ms 5,376 KB
testcase_07	AC	394 ms 5,376 KB
testcase_08	AC	402 ms 5,376 KB
testcase_09	AC	382 ms 5,376 KB
testcase_10	AC	387 ms 5,376 KB
testcase_11	AC	340 ms 5,376 KB
testcase_12	AC	304 ms 5,376 KB
testcase_13	AC	396 ms 5,376 KB
testcase_14	AC	408 ms 5,376 KB
testcase_15	AC	363 ms 5,376 KB
testcase_16	AC	377 ms 5,376 KB
testcase_17	AC	320 ms 5,376 KB
testcase_18	AC	296 ms 5,376 KB
testcase_19	AC	669 ms 5,376 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	311 ms 5,376 KB
testcase_23	AC	226 ms 5,376 KB
testcase_24	AC	216 ms 5,376 KB
testcase_25	AC	106 ms 5,376 KB
testcase_26	AC	243 ms 5,376 KB
testcase_27	AC	212 ms 5,376 KB
testcase_28	AC	137 ms 5,376 KB
testcase_29	AC	106 ms 5,376 KB
testcase_30	AC	140 ms 5,376 KB
testcase_31	AC	136 ms 5,376 KB
testcase_32	AC	21 ms 5,376 KB
testcase_33	AC	63 ms 5,376 KB
testcase_34	AC	82 ms 5,376 KB
testcase_35	AC	47 ms 5,376 KB
testcase_36	AC	246 ms 5,376 KB
testcase_37	AC	291 ms 5,376 KB
testcase_38	AC	104 ms 5,376 KB
testcase_39	AC	311 ms 5,376 KB
testcase_40	AC	119 ms 5,376 KB
testcase_41	AC	98 ms 5,376 KB
testcase_42	AC	645 ms 5,376 KB
testcase_43	AC	649 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#pragma GCC target("avx")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vs = vector<string>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(a,b,c,name,...) name
#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)
#define rrep4(i,a,b,c) for(ll i = (a) + ((b)-(a)-1) / (c) * (c);i >= (a);i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(i) begin(i) , end(i)
#define all2(i,a) begin(i) , begin(i) + a
#define all3(i,a,b) begin(i) + a , begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){return *min_element(all(a));}
template<class T> auto max(const T& a){return *max_element(all(a));}
template<class... Ts> void in(Ts&... t);
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
ll intpow(ll a, ll b){ ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}
ll modpow(ll a, ll b, ll p){ ll ans = 1; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll GCD(ll a,ll b) { if(a == 0 || b == 0) return 0; if(a % b == 0) return b; else return GCD(b,a%b);}
ll LCM(ll a,ll b) { if(a == 0) return b; if(b == 0) return a;return a / GCD(a,b) * b;}
namespace IO{
#define VOID(a) decltype(void(a))
struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(12);}} setting;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){
    in(get<idx>(t)...);}
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){
    ituple(t, make_index_sequence<tuple_size<T>::value>{});}
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }
#undef unpack
static const double PI = 3.1415926535897932;
template <class F> struct REC {
    F f;
    REC(F &&f_) : f(forward<F>(f_)) {}
    template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};
//constexpr int mod = 1000000007;
constexpr int mod = 998244353;
using Real = long double;
using Point = complex<Real>;
using Points = vector<Point>;
constexpr Real EPS = 1e-9;
istream &operator>>(istream &is,Point &p) {
    Real a,b;
    is >> a >> b;
    p = Point(a,b);
    return is;
}
ostream &operator<<(ostream &os,Point &p) {
    return os << real(p) << " " << imag(p);
}
inline bool eq(Real a,Real b) {return fabsl(b - a) < EPS;}
Point operator*(const Point &p,const Real &d) {
    return Point(real(p)*d,imag(p)*d);
}
namespace std {
bool operator<(const Point &a,const Point &b) {
    return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
}
}
//距離
Real distance(Point &a,Point &b) {
    return hypotl(a.real() - b.real(),a.imag() - b.imag());
}
//回転(rad)
Point rotate(Real theta, const Point &p) {
  return Point(cos(theta) * p.real() - sin(theta) * p.imag(), sin(theta) * p.real() + cos(theta) * p.imag());
}
//外積
Real cross(const Point &a,const Point &b) {
    return real(a) * imag(b) - imag(a) * real(b);
}
//内積
Real dot(const Point &a,const Point &b) {
    return real(a) * real(b) + imag(a) * imag(b);
}
int ccw(const Point &a,Point b,Point c) {
    b = b - a, c = c - a;
    if(cross(b,c) > EPS) return +1;  //反時計回り
    if(cross(b,c) < -EPS) return -1; //時計回り
    if(dot(b,c) < 0) return +2;      //b-a-c
    if(norm(b) < norm(c)) return -2; //a-b-c
    return 0;                        //a-c-b
}
// a-bベクトルとb-cベクトルのなす角
Real get_angle(const Point &a,const Point &b,const Point &c) {
    const Point v(b - a), w(c - b);
    Real alpha = atan2(v.imag(),v.real()), beta = atan2(w.imag(),w.real());
    if(alpha > beta) swap(alpha,beta);
    Real theta = beta - alpha;
    return min(theta,2 * acosl(-1) - theta);
}
using Polygon = vector<Point>;
Polygon convex_hull(vector<Point> ps) {
    int n = (int)ps.size(),k = 0;
    if(n <= 2) return ps;
    sort(ps.begin(),ps.end());
    vector<Point> ch(2*n);
    for(int i = 0;i < n;ch[k++] = ps[i++]) {
        while(k >= 2 && cross(ch[k-1]-ch[k-2],ps[i]-ch[k-1]) < EPS) --k;
    }
    for(int i = n - 2,t = k + 1;i >= 0;ch[k++] = ps[i--]) {
        while(k >= t && cross(ch[k-1]-ch[k-2],ps[i]-ch[k-1]) < EPS) --k;
    }
    ch.resize(k-1);
    return ch;
}
Real area(const Polygon &p) {
    Real A = 0;
    for(int i = 0;i < (int)p.size();++i) {
        A += cross(p[i],p[(i+1) % p.size()]);
    }
    return A * .5;
}

struct Circle {
    Point p;
    Real r;
    Circle() = default;
    Circle(Point _p,Real _r):p(_p),r(_r){}
};
int intersect(Circle c1,Circle c2) {
    if(c1.r < c2.r) swap(c1,c2);
    Real d = abs(c1.p - c2.p);
    if(c1.r + c2.r < d) return 4;   //円が離れている
    if(eq(c1.r + c2.r,d)) return 3; //円の外部と外部が接している
    if(c1.r - c2.r < d) return 2;   //円が交わっている
    if(eq(c1.r - c2.r,d)) return 1; //一方の円の内部ともう一方の円の外部と接している
    return 0;                       //一方の円の内部にもう一方の円がある
}
struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
    Line(Real A, Real B, Real C) // Ax + By = C
    {
        if(eq(A, 0)) a = Point(0, C / B), b = Point(1, C / B);
        else if(eq(B, 0)) a = Point(C / A, 0), b = Point(C / A, 1);
        else a = Point(0, C / B), b = Point(C / A, 0);
    }
    friend ostream &operator<<(ostream &os, Line &p) {
        return os << p.a << " to " << p.b;
    }
    friend istream &operator>>(istream &is, Line &a) {
        return is >> a.a >> a.b;
    }
};

bool parallel(const Line &a, const Line &b) {
    return eq(cross(a.b - a.a, b.b - b.a), 0.0);
}
Point projection(const Line &l, const Point &p) {
    double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}
Real distance(const Line &l, const Point &p) {
    return abs(p - projection(l, p));
}
bool intersect(const Circle &c, const Line &l) {
    return distance(l, c.p) <= c.r + EPS;
}
Point crosspoint(const Line &l, const Line &m) {
    Real A = cross(l.b - l.a, m.b - m.a);
    Real B = cross(l.b - l.a, l.b - m.a);
    if(eq(abs(A), 0.0) && eq(abs(B), 0.0)) return m.a;
    return m.a + (m.b - m.a) * B / A;
}
pair<Point,Point> crosspoint(const Circle &c, const Line l) {
    Point pr = projection(l, c.p);
    Point e = (l.b - l.a) / abs(l.b - l.a);
    if(eq(distance(l, c.p), c.r)) return {pr, pr};
    double base = sqrt(c.r * c.r - norm(pr - c.p));
    return {pr - e * base, pr + e * base};
}
pair<Point,Point> crosspoint(const Circle &c1,const Circle &c2) {
    Real d = abs(c1.p - c2.p);
    Real x = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d);
    if (abs(x) > 1) x = (x > 0 ? 1.0 : -1.0);
    Real a = acos(x);
    Real t = atan2(c2.p.imag() - c1.p.imag(), c2.p.real() - c1.p.real());
    Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
    Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
    return {p1, p2};
}
enum {
  OUT, ON, IN
};
 
int contains(const Polygon &Q, const Point &p) {
    bool in = false;
    for(int i = 0; i < Q.size(); i++) {
        Point a = Q[i] - p, b = Q[(i + 1) % Q.size()] - p;
        if(a.imag() > b.imag()) swap(a, b);
        if(a.imag() <= 0 && 0 < b.imag() && cross(a, b) < 0) in = !in;
        if(cross(a, b) == 0 && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}

int convex_contains(const Polygon &Q, const Point &p) {
    int N = (int) Q.size();
    Point g = (Q[0] + Q[N / 3] + Q[N * 2 / 3]) / (long double)3.0;
    if(g == p) return IN;
    Point gp = p - g;
    int l = 0, r = N;
    while(r - l > 1) {
        int mid = (l + r) / 2;
        Point gl = Q[l] - g;
        Point gm = Q[mid] - g;
        if(cross(gl, gm) > 0) {
            if(cross(gl, gp) >= 0 && cross(gm, gp) <= 0) r = mid;
            else l = mid;
        } 
        else {
            if(cross(gl, gp) <= 0 && cross(gm, gp) >= 0) l = mid;
            else r = mid;
        }
    }
    r %= N;
    Real v = cross(Q[l] - p, Q[r] - p);
    return eq(v, 0.0) ? ON : v < 0.0 ? OUT : IN;
}
template<typename T>
void warshall_floyd(vector<vector<T>> &g) {
    int n = g.size();
    for(int k = 0;k < n;k++) {
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                if(g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }
}
int main() {
    INT(n,m);
    vector<ld> x1(n),y1(n),x2(n),y2(n);
    rep(i,n) cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    vector<Line> lines(n);
    rep(i,n) {
        lines[i] = Line(Point{x1[i],y1[i]},Point{x2[i],y2[i]});
    }
    vector<vector<ld>> dist(2 * n,vector<ld>(2 * n,1e18));
    rep(i,2 * n) {
        dist[i][i] = 0;
        rep(j,2 * n) {
            if(i == j) continue;
            if((i - j + n) % n == 0) {
                int flg = 1;
                int now = i % n;
                rep(k,n) {
                    if(now == k) continue;
                    if(parallel(lines[now],lines[k])) continue;
                    auto p = crosspoint(lines[now],lines[k]);
                    if(abs(x1[now] - x2[now]) > EPS) {
                        if(min(x1[now],x2[now]) < p.real() && p.real() < max(x1[now],x2[now])) {
                            if(abs(x1[k] - x2[k]) > EPS) {
                                if(min(x1[k],x2[k]) < p.real() && p.real() < max(x1[k],x2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                            else {
                                if(min(y1[k],y2[k]) < p.imag() && p.imag() < max(y1[k],y2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                        }
                    }
                    else {
                        if(min(x1[now],x2[now]) < p.real() && p.real() < max(x1[now],x2[now])) {
                            if(abs(x1[k] - x2[k]) > EPS) {
                                if(min(x1[k],x2[k]) < p.real() && p.real() < max(x1[k],x2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                            else {
                                if(min(y1[k],y2[k]) < p.imag() && p.imag() < max(y1[k],y2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                        }
                    }
                }
                if(flg) {
                    dist[i][j] = hypotl(x1[now]-x2[now],y1[now]-y2[now]);
                }
            }
            else {
                Point p1 = (i >= n ? Point{x2[i-n],y2[i-n]} : Point{x1[i],y1[i]});
                Point p2 = (j >= n ? Point{x2[j-n],y2[j-n]} : Point{x1[j],y1[j]});
                Line l(p1,p2);
                int flg = 1;
                int ch1 = i % n,ch2 = j % n;
                rep(k,n) {
                    if(k == ch1 || k == ch2) continue;
                    if(parallel(l,lines[k])) continue;
                    auto p = crosspoint(l,lines[k]);
                    if(i == 5 && j == 7) {
                        debug(k,p.real(),p.imag());
                    }
                    if(abs(p1.real() - p2.real()) > EPS) {
                        if(min(p1.real(),p2.real()) < p.real() && p.real() < max(p1.real(),p2.real())) {
                            if(abs(x1[k] - x2[k]) > EPS) {
                                if(min(x1[k],x2[k]) < p.real() && p.real() < max(x1[k],x2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                            else {
                                if(min(y1[k],y2[k]) < p.imag() && p.imag() < max(y1[k],y2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                        }
                    }
                    else {
                        if(min(p1.imag(),p2.imag()) < p.imag() && p.imag() < max(p1.imag(),p2.imag())) {
                            if(abs(x1[k] - x2[k]) > EPS) {
                                if(min(x1[k],x2[k]) < p.real() && p.real() < max(x1[k],x2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                            else {
                                if(min(y1[k],y2[k]) < p.imag() && p.imag() < max(y1[k],y2[k])) {
                                    flg = 0;
                                    break;
                                }
                            }
                        }
                    }
                }
                if(i == 5 && j == 7) {
                    debug(flg);
                }
                if(flg) {
                    dist[i][j] = distance(p1,p2);
                }
            }
        }
    }
    //debug(dist);
    warshall_floyd<ld>(dist);
    //debug(dist);
    rep(i,m) {
        INT(a,b,c,d);
        a--,c--;
        if(b == 2) a += n;
        if(d == 2) c += n;
        cout << dist[a][c] << '\n';
    }
}

yukicoder

結果

テストケース

ソースコード