結果
問題 | No.2376 障害物競プロ |
ユーザー |
|
提出日時 | 2023-07-12 01:38:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 921 ms / 4,000 ms |
コード長 | 3,169 bytes |
コンパイル時間 | 1,509 ms |
コンパイル使用メモリ | 140,672 KB |
最終ジャッジ日時 | 2025-02-15 09:55:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <functional> #include <cmath> #include <iomanip> #include <stack> #include <queue> #include <numeric> #include <map> #include <unordered_map> #include <set> #include <fstream> #include <chrono> #include <random> #include <bitset> //#include <atcoder/all> #define rep(i,n) for(int i=0;i<(n);i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) ((int)(x).size()) #define pb push_back using ll = long long; using namespace std; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a, ll b) {return a/gcd(a,b)*b;} struct P{ ll x; ll y; }; bool cmp(const P& a, const P& b){ return pair<ll,ll>(a.x,a.y) < pair<ll,ll>(b.x,b.y); } struct L{ P a; P b; }; ll dot(P a, P b) { return (a.x * b.x + a.y * b.y); } ll cross(P a, P b) { return (a.x * b.y - a.y * b.x); } ll norm(P a){ return a.x*a.x+a.y*a.y; } double dist(L a){ ll dx = a.a.x - a.b.x; ll dy = a.a.y - a.b.y; return sqrt(dx*dx+dy*dy); } int ccw(P a, P b, P c) { b.x -= a.x, c.x -= a.x; b.y -= a.y, c.y -= a.y; if(cross(b, c) > 0) { return 1; } if(cross(b, c) < 0) { return -1; } if(dot(b, c) < 0) { return 2; } if(norm(b) < norm(c)) { return -2; } return 0; } bool isect(L s, L t) { return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0; } int main(){ int N,M; cin >> N >> M; vector<L> A(N); rep(i,N){ cin >> A[i].a.x >> A[i].a.y >> A[i].b.x >> A[i].b.y; } vector<P> PV(N*2); rep(i,N){ PV[i*2] = A[i].a; PV[i*2+1] = A[i].b; } sort(all(PV),cmp); vector<vector<double>> D(N*2,vector<double>(N*2,1e100)); rep(i,N*2) D[i][i] = 0; rep(i,N){ rep(j,i){ int ia = lower_bound(all(PV),A[i].a,cmp) - PV.begin(); int ib = lower_bound(all(PV),A[i].b,cmp) - PV.begin(); int ja = lower_bound(all(PV),A[j].a,cmp) - PV.begin(); int jb = lower_bound(all(PV),A[j].b,cmp) - PV.begin(); L aa = {A[i].a, A[j].a}; L ab = {A[i].a, A[j].b}; L ba = {A[i].b, A[j].a}; L bb = {A[i].b, A[j].b}; int okaa = 1, okab = 1, okba = 1, okbb = 1; rep(k,N){ if(k==i || k==j) continue; if(isect(aa,A[k])) okaa = 0; if(isect(ab,A[k])) okab = 0; if(isect(ba,A[k])) okba = 0; if(isect(bb,A[k])) okbb = 0; } if(okaa) D[ia][ja] = D[ja][ia] = dist(aa); if(okab) D[ia][jb] = D[jb][ia] = dist(ab); if(okba) D[ib][ja] = D[ja][ib] = dist(ba); if(okbb) D[ib][jb] = D[jb][ib] = dist(bb); } } rep(k,N*2) rep(i,N*2) rep(j,N*2) chmin(D[i][j],D[i][k]+D[k][j]); rep(i,M){ int a,b,c,d; cin >> a >> b >> c >> d; a--; c--; P p = (b==1)?(A[a].a):(A[a].b); P q = (d==1)?(A[c].a):(A[c].b); int f = lower_bound(all(PV),p,cmp) - PV.begin(); int t = lower_bound(all(PV),q,cmp) - PV.begin(); cout << fixed << setprecision(20) << D[f][t] << '\n'; } return 0; };