結果

問題 No.2376 障害物競プロ
ユーザー milanis48663220milanis48663220
提出日時 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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){};
      |              ^

ソースコード

diff #
プレゼンテーションモードにする

#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);
};
};
/**
* lp1, 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 = 0ax+by+c
*/
template<typename T>
T substitute(line<T> l, point<T> p){
return p.x*l.a+p.y*l.b+l.c;
}
/**
* lp1, 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, p2q1, 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);
}
/**
* l1l2
*/
bool intersect(line<double> l1, line<double> l2){
if(abs(l1.a*l2.b-l2.a*l1.b) < eps) return false;
return true;
}
/**
* l1l2
* 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0