結果
| 問題 | No.2376 障害物競プロ |
| ユーザー |
 siganai
|
| 提出日時 | 2023-07-07 23:05:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 15,304 bytes |
| コンパイル時間 | 3,087 ms |
| コンパイル使用メモリ | 219,036 KB |
| 実行使用メモリ | 5,064 KB |
| 最終ジャッジ日時 | 2023-09-29 00:48:54 |
| 合計ジャッジ時間 | 54,139 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,388 KB |
| testcase_01 | AC | 2 ms
4,384 KB |
| testcase_02 | AC | 2 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | AC | 212 ms
4,384 KB |
| testcase_05 | AC | 302 ms
4,388 KB |
| testcase_06 | AC | 130 ms
4,388 KB |
| testcase_07 | AC | 398 ms
4,696 KB |
| testcase_08 | AC | 400 ms
4,800 KB |
| testcase_09 | AC | 380 ms
4,756 KB |
| testcase_10 | AC | 389 ms
4,748 KB |
| testcase_11 | AC | 331 ms
4,692 KB |
| testcase_12 | AC | 307 ms
4,748 KB |
| testcase_13 | AC | 382 ms
4,524 KB |
| testcase_14 | AC | 393 ms
4,800 KB |
| testcase_15 | AC | 359 ms
4,664 KB |
| testcase_16 | AC | 384 ms
4,740 KB |
| testcase_17 | AC | 313 ms
4,808 KB |
| testcase_18 | AC | 298 ms
4,756 KB |
| testcase_19 | AC | 668 ms
4,756 KB |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | AC | 315 ms
4,384 KB |
| testcase_23 | AC | 223 ms
4,384 KB |
| testcase_24 | AC | 220 ms
4,384 KB |
| testcase_25 | AC | 107 ms
4,384 KB |
| testcase_26 | AC | 249 ms
4,384 KB |
| testcase_27 | AC | 213 ms
4,384 KB |
| testcase_28 | AC | 136 ms
4,384 KB |
| testcase_29 | AC | 109 ms
4,384 KB |
| testcase_30 | AC | 136 ms
4,492 KB |
| testcase_31 | AC | 135 ms
4,380 KB |
| testcase_32 | AC | 20 ms
4,384 KB |
| testcase_33 | AC | 61 ms
4,384 KB |
| testcase_34 | AC | 75 ms
4,384 KB |
| testcase_35 | AC | 43 ms
4,384 KB |
| testcase_36 | AC | 240 ms
4,508 KB |
| testcase_37 | AC | 289 ms
4,380 KB |
| testcase_38 | AC | 107 ms
4,384 KB |
| testcase_39 | AC | 307 ms
4,828 KB |
| testcase_40 | AC | 113 ms
4,580 KB |
| testcase_41 | AC | 99 ms
4,388 KB |
| testcase_42 | AC | 641 ms
4,756 KB |
| testcase_43 | AC | 653 ms
4,764 KB |
ソースコード
//#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-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-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;
assert(abs(A) >= EPS);
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(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(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';
}
}