結果

問題 No.2376 障害物競プロ
ユーザー pointNpointN
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
};
0