#889894 (C++17) No.2376 障害物競プロ

提出ソース

結果

問題	No.2376 障害物競プロ
ユーザー	pointN
提出日時	2023-07-12 01:38:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	920 ms / 4,000 ms
コード長	3,169 bytes
コンパイル時間	2,744 ms
コンパイル使用メモリ	143,220 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-10-11 16:01:09
合計ジャッジ時間	86,548 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,352 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	516 ms 4,348 KB
testcase_05	AC	718 ms 4,352 KB
testcase_06	AC	297 ms 4,352 KB
testcase_07	AC	915 ms 4,348 KB
testcase_08	AC	920 ms 4,352 KB
testcase_09	AC	904 ms 4,352 KB
testcase_10	AC	900 ms 4,352 KB
testcase_11	AC	816 ms 4,376 KB
testcase_12	AC	787 ms 4,380 KB
testcase_13	AC	881 ms 4,380 KB
testcase_14	AC	888 ms 4,376 KB
testcase_15	AC	829 ms 4,380 KB
testcase_16	AC	874 ms 4,380 KB
testcase_17	AC	775 ms 4,384 KB
testcase_18	AC	758 ms 4,380 KB
testcase_19	AC	805 ms 4,380 KB
testcase_20	AC	828 ms 4,380 KB
testcase_21	AC	826 ms 4,376 KB
testcase_22	AC	715 ms 4,384 KB
testcase_23	AC	485 ms 4,376 KB
testcase_24	AC	534 ms 4,380 KB
testcase_25	AC	255 ms 4,376 KB
testcase_26	AC	587 ms 4,380 KB
testcase_27	AC	507 ms 4,376 KB
testcase_28	AC	293 ms 4,380 KB
testcase_29	AC	254 ms 4,384 KB
testcase_30	AC	276 ms 4,380 KB
testcase_31	AC	303 ms 4,376 KB
testcase_32	AC	37 ms 4,384 KB
testcase_33	AC	118 ms 4,380 KB
testcase_34	AC	154 ms 4,376 KB
testcase_35	AC	103 ms 4,380 KB
testcase_36	AC	525 ms 4,384 KB
testcase_37	AC	666 ms 4,380 KB
testcase_38	AC	240 ms 4,380 KB
testcase_39	AC	687 ms 4,380 KB
testcase_40	AC	215 ms 4,380 KB
testcase_41	AC	232 ms 4,380 KB
testcase_42	AC	890 ms 4,384 KB
testcase_43	AC	890 ms 4,384 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード