結果

問題 No.2376 障害物競プロ
ユーザー tnakao0123tnakao0123
提出日時 2024-06-26 09:49:26
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 361 ms / 4,000 ms
コード長 2,693 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 60,356 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 09:50:19
合計ジャッジ時間 52,663 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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

/* -*- coding: utf-8 -*-
*
* 2376.cc: No.2376 ョウΟ - yukicoder
*/
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
/* constant */
const int MAX_N = 150;
const int MAX_GN = MAX_N * 2;
const double DINF = 1e60;
/* typedef */
typedef long long ll;
template <typename T>
struct Pt {
T x, y;
Pt() {}
Pt(T _x, T _y) : x(_x), y(_y) {}
Pt(const Pt<T> &p) : x(p.x), y(p.y) {}
Pt<T> operator+(const Pt<T> p) const { return Pt<T>(x + p.x, y + p.y); }
Pt<T> operator-() const { return Pt<T>(-x, -y); }
Pt<T> operator-(const Pt<T> p) const { return Pt<T>(x - p.x, y - p.y); }
Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
T dot(Pt<T> v) const { return x * v.x + y * v.y; }
T cross(Pt<T> v) const { return x * v.y - y * v.x; }
Pt<T> mid(const Pt<T> p) { return Pt<T>((x + p.x) / 2, (y + p.y) / 2); }
T d2() { return x * x + y * y; }
double d() { return sqrt(d2()); }
Pt<T> rot(double th) {
double c = cos(th), s = sin(th);
return Pt<T>(c * x - s * y, s * x + c * y);
}
Pt<T> rot90() { return Pt<T>(-y, x); }
bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
bool operator<(const Pt<T> &pt) const {
return x < pt.x || (x == pt.x && y < pt.y);
}
void print() { printf("(%d,%d)", x, y); }
};
using pt = Pt<int>;
/* global variables */
pt ps[MAX_GN];
double ds[MAX_GN][MAX_GN];
/* subroutines */
bool cross_segs(const pt& a0, const pt& a1, const pt& b0, const pt& b1) {
pt va(a1 - a0), vb(b1 - b0);
return
(ll)va.cross(b0 - a0) * va.cross(b1 - a0) < 0 &&
(ll)vb.cross(a0 - b0) * vb.cross(a1 - b0) < 0;
}
/* main */
int main() {
int n, m;
scanf("%d%d", &n, &m);
int gn = 0;
for (int i = 0; i < n; i++) {
int x0, y0, x1, y1;
scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
ps[gn++] = pt(x0, y0), ps[gn++] = pt(x1, y1);
}
for (int i = 0; i < gn; i++) {
ds[i][i] = 0.0;
for (int j = i + 1; j < gn; j++) {
ds[i][j] = ds[j][i] = DINF;
int ei = i >> 1, ej = j >> 1;
if (ei != ej) {
bool ok = true;
for (int k = 0; ok && k < n; k++)
if (k != ei && k != ej)
ok = ! cross_segs(ps[i], ps[j], ps[k * 2], ps[k * 2 + 1]);
if (ok)
ds[i][j] = ds[j][i] = (ps[j] - ps[i]).d();
}
}
}
for (int k = 0; k < gn; k++)
for (int i = 0; i < gn; i++)
for (int j = 0; j < gn; j++)
ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
while (m--) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
a--, b--, c--, d--;
int i = a * 2 + b, j = c * 2 + d;
printf("%.10lf\n", ds[i][j]);
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0