#783061 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	ronnya
提出日時	2022-07-30 16:03:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	5,200 bytes
コンパイル時間	2,152 ms
実行使用メモリ	3,612 KB
スコア	3,914,005
最終ジャッジ日時	2022-07-30 16:03:44
合計ジャッジ時間	3,630 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 3,440 KB
testcase_01	AC	2 ms 3,584 KB
testcase_02	AC	1 ms 3,440 KB
testcase_03	AC	2 ms 3,560 KB
testcase_04	AC	1 ms 3,540 KB
testcase_05	AC	2 ms 3,556 KB
testcase_06	AC	2 ms 3,440 KB
testcase_07	AC	2 ms 3,612 KB
testcase_08	AC	1 ms 3,540 KB
testcase_09	AC	1 ms 3,540 KB
testcase_10	AC	1 ms 3,604 KB
testcase_11	AC	1 ms 3,556 KB
testcase_12	AC	1 ms 3,500 KB
testcase_13	AC	1 ms 3,560 KB
testcase_14	AC	1 ms 3,552 KB
testcase_15	AC	1 ms 3,552 KB
testcase_16	AC	1 ms 3,528 KB
testcase_17	AC	1 ms 3,440 KB
testcase_18	AC	1 ms 3,528 KB
testcase_19	AC	1 ms 3,492 KB
testcase_20	AC	2 ms 3,564 KB
testcase_21	AC	1 ms 3,588 KB
testcase_22	AC	1 ms 3,508 KB
testcase_23	AC	1 ms 3,600 KB
testcase_24	AC	1 ms 3,588 KB
testcase_25	AC	1 ms 3,440 KB
testcase_26	AC	1 ms 3,504 KB
testcase_27	AC	2 ms 3,604 KB
testcase_28	AC	1 ms 3,572 KB
testcase_29	AC	1 ms 3,492 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>

using namespace std;

using ll   = long long;     using ld   = long double;
using pll  = pair<ll, ll>;  using pld  = pair<ld, ld>;
using vll  = vector<ll>;    using vld  = vector<ld>;
using vpll = vector<pll>;   using vpld = vector<pld>;
using vvll = vector<vll>;   using vvld = vector<vld>;
template<class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

#define rep(i, a, b) for(ll i = (ll)a; i < (ll)b; i++)
#define irep(i, v) for(auto i = (v).begin(); i != (v).end(); i++)
#define SZ(v) (ll)(v).size()
#define ALL(v) (v).begin(), (v).end()
#define SHIFT(a) (1LL << (ll)a)
#define endl '\n'

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-10;
const ld PI  = M_PI;

ll power(ll x, ll y){ ll res = 1; while(y > 0){ if(y & 1){ res *= x; } x *= x; y >>= 1; } return res; }
bool in_grid(ll x, ll y, ll h, ll w){ return (0 <= x && x < h && 0 <= y && y < w); }
template<class T> void pvec(vector<T> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ if(i){ cout << " "; } cout << vec[i]; } cout << endl; }
template<class T> void pvvec(vector<vector<T>> &vec){ for(ll i = 0; i < (ll)vec.size(); i++){ for(ll j = 0; j < (ll)vec[i].size(); j++){ if(j){ cout << " "; } cout << vec[i][j]; } cout << endl; } }
template<class T> void asort(vector<T> &vec){ sort(ALL(vec)); }
template<class T> void rsort(vector<T> &vec){ sort(ALL(vec)); reverse(ALL(vec)); }

void pr(pll p){
  cout << p.first << " " << p.second << endl;
}

using ppll = pair<pll, pll>;

bool comp1(ppll &p1, ppll &p2){
  return (p1.first.first < p2.first.first);
}

bool comp2(ppll &p1, ppll &p2){
  return (p1.first.first > p2.first.first);
}

ll dis(pll &p1, pll &p2){
  ll res = (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
  return res;
}



//using mint = modint<MOD>;

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  cout << fixed << setprecision(20);

  ll n, m;
  cin >> n >> m;
  vpll vec(n);
  rep(i, 0, n) cin >> vec[i].first >> vec[i].second;



  vector<ppll> vec1, vec2, vec3, vec4;

  ll x = vec[0].first, y = vec[0].second;
  rep(i, 1, n){
    ll xp = vec[i].first, yp = vec[i].second;
    if(xp >= x && yp < y) vec1.push_back({vec[i], {1, i + 1}});
    if(xp > x && yp >= y) vec2.push_back({vec[i], {1, i + 1}});
    if(xp <= x && yp > y) vec3.push_back({vec[i], {1, i + 1}});
    if(xp < x && yp <= y) vec4.push_back({vec[i], {1, i + 1}});
  }

  vpll sta(m);
/*
  rep(i, 0, m){
    sta[i] = {rand() % 1000, rand() % 1000};
    pr(sta[i]);
  }

  rep(i, 0, m){
    ll xp = sta[i].first, yp = sta[i].second;
    if(xp >= x && yp < y) vec1.push_back({sta[i], {2, i + 1}});
    if(xp > x && yp >= y) vec2.push_back({sta[i], {2, i + 1}});
    if(xp <= x && yp > y) vec3.push_back({sta[i], {2, i + 1}});
    if(xp < x && yp <= y) vec4.push_back({sta[i], {2, i + 1}});
  }
  */


  
  sort(ALL(vec1), comp1); 
  sort(ALL(vec2), comp2);
  sort(ALL(vec3), comp2);
  sort(ALL(vec4), comp1);

  vll points = {0};
  rep(i, 0, SZ(vec1)) points.push_back(vec1[i].second.second - 1);
  rep(i, 0, SZ(vec2)) points.push_back(vec2[i].second.second - 1);
  rep(i, 0, SZ(vec3)) points.push_back(vec3[i].second.second - 1);
  rep(i, 0, SZ(vec4)) points.push_back(vec4[i].second.second - 1);
  points.push_back(0);

  max_queue<pair<ll, pll>> que;
  rep(i, 0, SZ(points) - 1){
    ll x1 = vec[points[i]].first, y1 = vec[points[i]].second;
    ll x2 = vec[points[i + 1]].first, y2 = vec[points[i + 1]].second;
    ll d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    que.push({d, {points[i], points[i + 1]}});
  }

  rep(i, 0, m){
    auto tmp = que.top().second; que.pop();
    pll p1 = vec[tmp.first], p2 = vec[tmp.second];
    sta[i] = {(p1.first + p2.first) / 2, (p1.second + p2.second) / 2};
    //sta[i] = {rand() % 1000, rand() % 1000};
  }


  rep(i, 0, m){
    pr(sta[i]);
    ll xp = sta[i].first, yp = sta[i].second;
    if(xp >= x && yp < y) vec1.push_back({sta[i], {2, i + 1}});
    if(xp > x && yp >= y) vec2.push_back({sta[i], {2, i + 1}});
    if(xp <= x && yp > y) vec3.push_back({sta[i], {2, i + 1}});
    if(xp < x && yp <= y) vec4.push_back({sta[i], {2, i + 1}});
  }

  sort(ALL(vec1), comp1); 
  sort(ALL(vec2), comp2);
  sort(ALL(vec3), comp2);
  sort(ALL(vec4), comp1);


  vpll ans = {{1, 1}};

  rep(i, 0, SZ(vec1)) ans.push_back(vec1[i].second);
  rep(i, 0, SZ(vec2)) ans.push_back(vec2[i].second);
  rep(i, 0, SZ(vec3)) ans.push_back(vec3[i].second);
  rep(i, 0, SZ(vec4)) ans.push_back(vec4[i].second);

  ans.push_back({1, 1});


  vpll res;
  rep(i, 0, SZ(ans) - 1){
    res.push_back(ans[i]);
    pll p1 = vec[ans[i].second - 1];
    pll p2 = vec[ans[i + 1].second - 1];
    ll d1 = dis(p1, p2);
    if(ans[i].first == 1 && ans[i + 1].first == 1){
      rep(j, 0, m){
        pll p3 = sta[j];
        ld d2 = dis(p1, p3);
        ld d3 = dis(p3, p2);
        if(5.0 * d2 + 5.0 * d3 < 25 * d1){
          res.push_back({2, j + 1});
          continue;
        }
      }
    }
  }

  res.push_back({1, 1});

  cout << SZ(res) << endl;
  rep(i, 0, SZ(res)) pr(res[i]);



  return 0;
}

yukicoder

結果

テストケース

ソースコード