結果
問題 | 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;}}