結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-07 23:02:18 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,592 bytes |
コンパイル時間 | 3,235 ms |
コンパイル使用メモリ | 142,236 KB |
最終ジャッジ日時 | 2025-02-15 08:16:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:71:15: error: expected ')' before 'x' 71 | point<T>(T x, T y): x(x), y(y){}; | ~ ^~ | ) main.cpp:72:14: error: expected unqualified-id before ')' token 72 | point<T>(): x(0), y(0){}; | ^
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <tuple> #include <cmath> #include <numeric> #include <functional> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template<typename T> vector<vector<T>> vec2d(int n, int m, T v){ return vector<vector<T>>(n, vector<T>(m, v)); } template<typename T> vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){ return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v))); } template<typename T> void print_vector(vector<T> v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } template<typename T> struct line { line(T a, T b, T c): a(a), b(b), c(c){}; T a, b, c; }; template<typename T> ostream& operator<<(ostream& os, const line<T>& l){ os << l.a << "*x + " << l.b << "*y+ " << l.c; return os; } template<typename T> inline T add(T a, T b){ return a+b; } const double eps = 1e-10; inline double add(double a, double b){ if(abs(a+b) < eps*(abs(a)+abs(b))) return 0.0; return a+b; } template<typename T> class point { public: point<T>(T x, T y): x(x), y(y){}; point<T>(): x(0), y(0){}; T x, y; point<T> operator + (point<T> p){ return point<T>(add(x, p.x), add(y, p.y)); }; point<T> operator - (point<T> p){ return point<T>(add(x, -p.x), add(y, -p.y)); }; point<T> operator * (T d){ return point<T>(x*d, y*d); }; T dot(point<T> p){ return add(x*p.x, y*p.y); }; T det(point<T> p){ return add(x*p.y, -y*p.x); }; }; /** * 直線lとp1, p2を結ぶ直線を求めます */ template<typename T> line<T> from_points(point<T> p1, point<T> p2){ return line(p2.y-p1.y, p1.x-p2.x, p1.y*p2.x-p1.x*p2.y); } /** * l: ax+by+c = 0としたときにax+by+cの値を返します */ template<typename T> T substitute(line<T> l, point<T> p){ return p.x*l.a+p.y*l.b+l.c; } /** * 直線lとp1, p2を結ぶ線分が交点を持つか否かを返します */ template<typename T> bool intersect(line<T> l, point<T> p1, point<T> p2){ return (substitute(l, p1) > 0) ^ (substitute(l, p2) > 0); } /** * p1, p2を結ぶ線分とq1, q2を結ぶ線分が交点を持つか否かを返します */ template<typename T> bool intersect(point<T> p1, point<T> p2, point<T> q1, point<T> q2){ auto lp = from_points(p1, p2); auto lq = from_points(q1, q2); bool fq = (substitute(lq, p1) > 0) ^ (substitute(lq, p2) > 0); bool fp = (substitute(lp, q1) > 0) ^ (substitute(lp, q2) > 0); return fp&&fq; } template<typename T> double dist(point<T> p1, point<T> p2){ T dx = p1.x-p2.x; T dy = p1.y-p2.y; return sqrt(dx*dx+dy*dy); } template<typename T> T dist_sq(point<T> p1, point<T> p2){ T dx = p1.x-p2.x; T dy = p1.y-p2.y; return dx*dx+dy*dy; } /** * 線分p1p2の垂直二等分線を求めます */ line<double> vertical_bisector(point<double> p1, point<double> p2){ double a = 2.0*(p2.x-p1.x); double b = 2.0*(p2.y-p1.y); double c = p2.x*p2.x-p1.x*p1.x+p2.y*p2.y-p1.y*p1.y; return line<double>(a, b, -c); } /** * 直線l1と直線l2がただ一つの交点を持つかを返します */ bool intersect(line<double> l1, line<double> l2){ if(abs(l1.a*l2.b-l2.a*l1.b) < eps) return false; return true; } /** * 直線l1と直線l2の交点を求めます * 戻り値をoptionalに書き換えるほうが良さそう */ point<double> intersection(line<double> l1, line<double> l2){ assert(intersect(l1, l2)); double x = l1.b*l2.c-l2.b*l1.c; double y = l2.a*l1.c-l1.a*l2.c; double d = l1.a*l2.b-l2.a*l1.b; return point<double>(x/d, y/d); } point<double> rot(double theta, point<double> p){ double x = p.x; double y = p.y; double c = cos(theta); double s = sin(theta); return point<double>(c*x-s*y, c*y+s*x); } const double INF = 1e+15; vector<vector<double>> warshallfloyd(vector<vector<double>> g){ int n = g.size(); vector<vector<double>> dist(n, vector<double>(n)); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ dist[i][j] = g[i][j]; } dist[i][i] = 0; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ double new_len = dist[j][i] + dist[i][k]; dist[j][k] = min(new_len, dist[j][k]); } } } return dist; } using Po = point<int>; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n, m; cin >> n >> m; vector<vector<Po>> points; for(int i = 0; i < n; i++){ points.push_back({}); for(int j = 0; j < 2; j++){ int x, y; cin >> x >> y; points.back().push_back(Po(x, y)); } } auto to_idx = [&](int i, int j){ return i*2+j; }; auto g = vec2d(n*2, n*2, INF); for(int i = 0; i < n; i++){ for(int j = 0; j < 2; j++){ for(int k = 0; k < n; k++){ for(int l = 0; l < 2; l++){ if(i == k) continue; bool ok = true; for(int p = 0; p < n; p++){ if(p == i || p == k) continue; if(intersect(points[i][j], points[k][l], points[p][0], points[p][1])) ok = false; } if(ok){ int idx0 = to_idx(i, j); int idx1 = to_idx(k, l); g[idx0][idx1] = dist(points[i][j], points[k][l]); // cout << i << ' ' << j << "->" << k << ' ' << l << ':' << g[idx0][idx1] << endl; } } } } } auto dist = warshallfloyd(g); for(int i = 0; i < m; i++){ int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; d--; int i0 = to_idx(a, b); int i1 = to_idx(c, d); cout << dist[i0][i1] << endl; } }