結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-25 12:47:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 899 ms / 4,000 ms |
コード長 | 3,589 bytes |
コンパイル時間 | 2,369 ms |
コンパイル使用メモリ | 204,292 KB |
最終ジャッジ日時 | 2025-02-15 18:56:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;// vector OA = (x, y)template <typename T>struct vec{T x, y;vec (T xx=0, T yy=0) : x(xx), y(yy) {};vec operator-() const {return vec(-x, -y);}vec& operator+=(const vec &w) {x += w.x; y += w.y;return *this;}vec& operator-=(const vec &w) {x -= w.x; y -= w.y;return *this;}vec operator+(const vec &w) const {vec res(*this);return res += w;}vec operator-(const vec &w) const {vec res(*this);return res-=w;}};//Inner product of vectors v and wtemplate <typename T>T dot(vec<T> v, vec<T> w){return v.x * w.x + v.y * w.y;}//Outer product of vector v and wtemplate <typename T>T outer(vec<T> v, vec<T> w){return v.x * w.y - w.x * v.y;}//size of triangle ABCtemplate <typename T>T heron(vec<T> &a, vec<T> &b, vec<T> &c){return abs(outer(b-a, c-a)) / 2;}//Distance between point a and btemplate <typename T>T distance(vec<T> &a, vec<T> &b){return sqrt(dot(a-b, a-b));}//Convex Hull(Smallest Convex set containing all given vecs)//Grahum Scan (O(NlogN))template <typename T>vector<vec<T>> convex_hull(vector<vec<T>> P){sort(P.begin(), P.end(), [](vec<T> &p1, vec<T> &p2) {if (p1.x != p2.x) return p1.x < p2.x;return p1.y < p2.y;});int N=P.size(), k=0, t;vector<vec<T>> res(N*2);for (int i=0; i<N; i++){while(k > 1 && outer(res[k-1]-res[k-2], P[i]-res[k-1]) <= 0) k--;res[k] = P[i];k++;}t = k;for (int i=N-2; i>=0; i--){while(k > t && outer(res[k-1]-res[k-2], P[i]-res[k-1]) <= 0) k--;res[k] = P[i];k++;}res.resize(k-1);return res;}//distance between line PQ and point Rtemplate <typename T>T dist_line_point(vec<T> &p, vec<T> &q, vec<T> &r){// ax+by+c=0T a = (q.y-p.y), b = (p.x-q.x), c = -p.x*q.y + p.y*q.x;cout << a << " " << b << " " << c << endl;return abs(a*r.x+b*r.y+c) / sqrt(a*a+b*b);};//judge if line AB intersects line CDtemplate <typename T>bool intersect(vec<T> &a, vec<T> &b, vec<T> &c, vec<T> &d){T s1, t1, s2, t2;s1 = outer(b-a, c-a);t1 = outer(b-a, d-a);s2 = outer(d-c, a-c);t2 = outer(d-c, b-c);if (s1 * t1 < 0 && s2 * t2 < 0) return 1;return 0;}int main(){using ld = long double;ll N, Q, a, b, c, d, x, y;cin >> N >> Q;vector<vec<ll>> p(N*2);vector<vec<ld>> q(N*2);vector<vector<ld>> dist(N*2, vector<ld>(N*2, 1e18));for (int i=0; i<N*2; i++){cin >> x >> y;p[i] = vec(x, y);q[i] = vec((ld)x, (ld)y);}for (int i=0; i<N*2; i++){dist[i][i] = 0;for (int j=i+1; j<N*2; j++){bool f=1;for (int k=0; k<N; k++){if (intersect(p[i], p[j], p[2*k], p[2*k+1])) f=0;}if (f){dist[i][j] = dist[j][i] = distance(q[i], q[j]);}}}/*for (int i=0; i<N*2; i++){for (int j=0; j<N*2; j++) cout << dist[i][j] << " ";cout << 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++){dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);}}}while(Q){Q--;cin >> a >> b >> c >> d; a--; b--; c--; d--;cout << setprecision(18) << dist[a*2+b][c*2+d] << endl;}return 0;}