結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2023-01-06 22:52:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 3,000 ms |
コード長 | 2,274 bytes |
コンパイル時間 | 4,023 ms |
コンパイル使用メモリ | 257,988 KB |
最終ジャッジ日時 | 2025-02-10 00:14:42 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;//using mint = modint1000000007;//const int mod = 1000000007;//using mint = modint998244353;//const int mod = 998244353;const int INF = 1e9;const long long LINF = 1e18;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define endl "\n"#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }long long sqrt(long long n) {long long ok = 0;long long ng = 2 * INF + 10;while (1 < abs(ok - ng)) {long long c = (ng + ok) / 2;if ((c * c) <= n) ok = c;else ng = c;}//cout << n << " " << ok << endl;return ok;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n; cin >> n;vector<long long>x(n), y(n), t(n);rep(i, n) cin >> x[i] >> y[i] >> t[i];vector<pair<long long, P>>v;rep(i, n)rep2(j, i + 1, n) {if (t[i] == t[j]) {long long d2 = 0;d2 += (x[i] - x[j]) * (x[i] - x[j]);d2 += (y[i] - y[j]) * (y[i] - y[j]);v.push_back({ d2, {i,j} });//cout << i << j << "_" << d2 << endl;}else {long long d1, d0;d0 = x[i] * x[i] + y[i] * y[i];d1 = x[j] * x[j] + y[j] * y[j];if (d0 > d1)swap(d0, d1);long long ng = -1;long long ok = LINF + 1;long long sq = sqrt(4 * d0 * d1);while (1 < abs(ok - ng)) {long long mid = (ng + ok) / 2;auto check = [&]() {// (sqrt(d2)-sqrt(d1))^2<=mid// d1 + d2 - 2 * sqrt(d1*d2) <= mid * mid// d1 + d2 + mid * mid <= sqrt(4 * d1 * d2);return (d0 + d1 - mid <= sq);};if (check()) ok = mid;else ng = mid;}//cout << i << j << " " << ok << endl;v.push_back({ ok, {i,j} });}}sort(all(v));dsu uf(n);rep(i, v.size()) {uf.merge(v[i].second.first, v[i].second.second);if (uf.same(0, n - 1)) {cout << v[i].first << endl;break;}}return 0;}