結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2023-01-06 22:32:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 3,000 ms |
コード長 | 3,737 bytes |
コンパイル時間 | 1,212 ms |
コンパイル使用メモリ | 120,492 KB |
最終ジャッジ日時 | 2025-02-10 00:10:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}/*** https://kenkoooo.hatenablog.com/entry/2016/11/30/163533* より。Project Eularであまりにも使うので。*/__int128 parse(string &s) {__int128 ret = 0;for (int i = 0; i < s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret = 10 * ret + s[i] - '0';return ret;}istream & operator >> (istream &in, __int128_t &m){string s; cin >> s;m = parse(s);return in;}ostream &operator<<(std::ostream &dest, __int128_t value) {ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(ios_base::badbit);}}return dest;}using ll = __int128_t;struct UnionFind {vector<int> data;UnionFind(int size) : data(size, -1) {}bool unionSet(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;}return x != y;}bool findSet(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}};int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int n; cin >> n;vector<int> x(n), y(n), t(n);for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> t[i];auto ok = [&](ll p){UnionFind uf(n);for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){if(t[i] == t[j]){ll dx = x[i]-x[j];ll dy = y[i]-y[j];ll sum = dx*dx+dy*dy;if(sum <= p) uf.unionSet(i, j);}else{ll a = x[i]*x[i]+y[i]*y[i];ll b = x[j]*x[j]+y[j]*y[j];ll sum = a+b-p;if(sum <= 0 || sum*sum <= 4*a*b) uf.unionSet(i, j);}}}return uf.findSet(0, n-1);};if(ok(0)){cout << 0 << endl;return 0;}ll l = 0, r = 1e18;while(r-l > 1){ll p = (l+r)/2;if(ok(p)) r = p;else l = p;}cout << r << endl;}