結果
問題 | No.2376 障害物競プロ |
ユーザー |
|
提出日時 | 2023-07-07 22:27:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 414 ms / 4,000 ms |
コード長 | 4,110 bytes |
コンパイル時間 | 2,542 ms |
コンパイル使用メモリ | 174,424 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-21 18:37:51 |
合計ジャッジ時間 | 54,207 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template<class T> struct point{T x, y;point(): x(0), y(0){}point(T a, T b): x(a), y(b){}point& operator += (const point& rhs) {x += rhs.x, y += rhs.y; return *this;}point& operator -= (const point& rhs) {x -= rhs.x, y -= rhs.y; return *this;}point& operator *= (const T& rhs) {x *= rhs, y *= rhs; return *this;}point& operator /= (const T& rhs) {x /= rhs, y /= rhs; return *this;}point operator +() const { return *this; }point operator -() const { return point() - *this; }friend point operator + (const point& lhs, const point& rhs) {return point(lhs) += rhs;}friend point operator - (const point& lhs, const point& rhs) {return point(lhs) -= rhs;}friend point operator * (const point& lhs, const T& rhs) {return point(lhs) *= rhs;}friend point operator * (const T& lhs, const point& rhs) {return point(rhs) *= lhs;}friend point operator / (const point& lhs, const T& rhs) {return point(lhs) /= rhs;}friend T operator * (const point& lhs, const point& rhs) {return lhs.x * rhs.x + lhs.y * rhs.y;}friend T operator ^ (const point& lhs, const point& rhs) {return lhs.x * rhs.y - lhs.y * rhs.x;}friend bool operator == (const point& lhs, const point& rhs) {return (lhs.x == rhs.x && lhs.y == rhs.y);}friend istream& operator >> (istream& os, point& rhs) noexcept {os >> rhs.x >> rhs.y;return os;}friend constexpr ostream& operator << (ostream &os, const point& rhs) noexcept {return os << '('<< rhs.x << ',' << rhs.y << ')';}double norm(){return sqrt(x * x + y * y);}T norm2(){return x * x + y * y;}int orthant(){//第何象限かのベクトルを返す(0,0は0象限とする)if(x == 0 && y == 0)return 0;if(y > 0)return (x > 0 ? 1 : 2);return (x > 0 ? 4 : 3);}//偏角ソート->ベクトルの大きさの小さい順の優先度friend bool operator < (point lhs, point rhs){//tupleとかでソートできないときは&を外すと良いかもしれないint lo = lhs.orthant(), ro = rhs.orthant();if(lo != ro)return (lo < ro);T cv = (lhs ^ rhs);if(cv != 0)return (cv > 0);return (lhs.norm2() < rhs.norm2());}};template<class T> int ccw(point<T> A, point<T> B,point<T> P){point<T> S1 = B - A, S2 = P - A;T cv = S1 ^ S2;if(cv > 0) return -1;if(cv < 0) return 1;T dv = S1 * S2;if(dv < 0) return 2;if(dv > S1 * S1) return -2;return 0;}//線分ABと線分CDの交差判定template<class T> bool intersect(point<T> A, point<T> B, point<T> C, point<T> D){return (ccw(A, B, C) * ccw(A, B, D) <= 0 && ccw(C, D, A) * ccw(C, D, B) <= 0);}int main(){ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;vector<point<ll>> a(n), b(n), c(2 * n);for(int i = 0; i < n; i++){cin >> a[i] >> b[i];c[i] = a[i];c[i + n] = b[i];}int n2 = 2 * n;vector<vector<double>> A(n2, vector<double>(n2, 1ll << 60));for(int i = 0; i < n2; i++){for(int j = i + 1; j < n2; j++){bool flag = true;for(int k = 0; k < n; k++){if(a[k] == c[i] || a[k] == c[j]) continue;if(b[k] == c[i] || b[k] == c[j]) continue;if(intersect(a[k], b[k], c[i], c[j])){flag = false;break;}}if(flag){A[i][j] = A[j][i] = (c[i] - c[j]).norm();}}}for(int i = 0; i < n2; i++) A[i][i] = 0;for(int k = 0; k < n2; k++){for(int i = 0; i < n2; i++){for(int j = 0; j < n2; j++){A[i][j] = min(A[i][j], A[i][k] + A[k][j]);}}}cout << fixed << setprecision(15);while(m--){int a2, b2, c2, d2;cin >> a2 >> b2 >> c2 >> d2;a2--, b2--, c2--, d2--;cout << A[a2 + b2 * n][c2 + d2 * n] << '\n';}}