結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-07 23:08:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 635 ms / 4,000 ms |
コード長 | 15,277 bytes |
コンパイル時間 | 2,317 ms |
コンパイル使用メモリ | 216,764 KB |
最終ジャッジ日時 | 2025-02-15 08:23:53 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
//#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))#endifusing 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 unpackstatic 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-10;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-cif(norm(b) < norm(c)) return -2; //a-b-creturn 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 == 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(y1[now],y2[now]) < p.imag() && p.imag() < max(y1[now],y2[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(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(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';}}