結果

問題 No.5007 Steiner Space Travel
ユーザー ronnyaronnya
提出日時 2022-07-30 16:55:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,383 bytes
コンパイル時間 2,177 ms
実行使用メモリ 5,160 KB
スコア 4,411,674
最終ジャッジ日時 2022-07-30 16:55:10
合計ジャッジ時間 3,614 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,904 KB
testcase_01 AC 1 ms
4,904 KB
testcase_02 AC 1 ms
4,900 KB
testcase_03 AC 1 ms
5,156 KB
testcase_04 AC 1 ms
5,160 KB
testcase_05 AC 2 ms
4,904 KB
testcase_06 AC 2 ms
5,156 KB
testcase_07 AC 1 ms
4,904 KB
testcase_08 AC 2 ms
4,904 KB
testcase_09 AC 2 ms
4,908 KB
testcase_10 AC 1 ms
5,160 KB
testcase_11 AC 1 ms
4,900 KB
testcase_12 AC 2 ms
4,904 KB
testcase_13 AC 1 ms
4,904 KB
testcase_14 AC 1 ms
4,900 KB
testcase_15 AC 2 ms
4,904 KB
testcase_16 AC 2 ms
5,160 KB
testcase_17 AC 1 ms
4,900 KB
testcase_18 AC 1 ms
5,160 KB
testcase_19 AC 1 ms
4,904 KB
testcase_20 AC 1 ms
5,156 KB
testcase_21 AC 2 ms
4,900 KB
testcase_22 AC 2 ms
4,900 KB
testcase_23 AC 1 ms
4,900 KB
testcase_24 AC 2 ms
4,900 KB
testcase_25 AC 2 ms
4,900 KB
testcase_26 AC 1 ms
5,160 KB
testcase_27 AC 1 ms
4,904 KB
testcase_28 AC 2 ms
4,900 KB
testcase_29 AC 2 ms
4,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

ll n, m;
vpll vec(100);
vpll sta(8);

vpll route;

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

ll total(vpll &r){
  ll res = 0;
  rep(i, 0, SZ(r) - 1){
    ll d;
    pll p1 = (r[i].first == 1 ? vec[r[i].second] : sta[r[i].second]);
    pll p2 = (r[i + 1].first == 1 ? vec[r[i + 1].second] : sta[r[i + 1].second]);
    if(r[i].first == 1 && r[i + 1].first == 1){
      d = 25 * dis(p1, p2);
    }
    else if(r[i].first == 2 && r[i + 1].first == 2){
      d = dis(p1, p2);
    }
    else{
      d = 5 * dis(p1, p2);
    }
    res += d;
  }
  return res;
}

//cout << ll(1000000000 / (1000 + sqrt(total(tmp)))) << endl;



//using mint = modint<MOD>;

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

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

  vector<pair<ld, ll>> rad;
  rep(i, 1, n){
    ll x = vec[i].first - vec[0].first;
    ll y = vec[i].second - vec[0].second;
    ld theta = atan2(y, x);
    rad.push_back({theta, i});
  }
  sort(ALL(rad));

  vpll tmp = {{1, 0}};
  rep(i, 0, SZ(rad)) tmp.push_back({1, rad[i].second});
  tmp.push_back({1, 0});

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

  vpll res;

  rep(i, 0, SZ(tmp) - 1){
    res.push_back(tmp[i]);
    pll p1 = vec[tmp[i].second], p2 = vec[tmp[i + 1].second];
    ll d1 = 25 * dis(p1, p2);
    min_queue<pll> que;
    rep(j, 0, SZ(sta)){
      pll p3 = sta[j];
      ll d2 = 5 * dis(p1, p3) + 5 * dis(p3, p2);
      que.push({d2, j});
    }
    pll p = que.top();
    if(p.first < d1) res.push_back({2, p.second});
  }
  res.push_back({1, 0});

  rep(i, 0, m) cout << sta[i].first << " " << sta[i].second << endl;
  cout << SZ(res) << endl;
  rep(i, 0, SZ(res)) cout << res[i].first << " " << res[i].second + 1 << endl;


  return 0;
}
0