結果
| 問題 | No.96 圏外です。 |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 17:13:09 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 568 ms / 5,000 ms |
| + 318µs | |
| コード長 | 5,340 bytes |
| 記録 | |
| コンパイル時間 | 3,995 ms |
| コンパイル使用メモリ | 296,540 KB |
| 実行使用メモリ | 17,664 KB |
| 最終ジャッジ日時 | 2026-11-16 17:13:21 |
| 合計ジャッジ時間 | 11,321 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
//python3 expander.py main.cpp
//export CPLUS_INCLUDE_PATH="/home/yantaro/kyopro/ac-library-master"
//https://github.com/yantaro-yanchan/kyopro-library/tree/master/library
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lll = __int128_t;
using ulll = __uint128_t;
//using mint = modint; //mint::set_mod(M);
//using mint = modint998244353;
//using mint = modint1000000007;
template<class T> using pq = priority_queue<T>; //大きい順
template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; //小さい順
#define vec_unique(v) v.erase(unique(v.begin(), v.end()), v.end()) //重複削除
#define vec_iota(v) iota(v.begin(), v.end(), 0) //0, 1, 2, 3, ..., n - 1にセット
#define concat(a, b) a.insert(a.end(), b.begin(), b.end())
#define debug(x) cerr << #x << " = " << x << endl
#define maxvalue(array) *max_element(array.begin(), array.end())
#define minvalue(array) *min_element(array.begin(), array.end())
#define sumvalue(array) accumulate(array.begin(), array.end(), 0ll)
#define popcount(x) __builtin_popcountll(x)
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
//int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
#define INF 2e18
#define INF2 2e9
pair<int, int> operator- (const pair<int, int> &a, const pair<int, int> &b) {
return {a.first - b.first, a.second - b.second};
}
ll cross(pair<int, int> l, pair<int, int> r) {
return (ll)l.first * r.second - (ll)l.second * r.first;
}
vector<pair<int, int>> Convex_Hull(vector<pair<int, int>> p) {
sort(p.begin(), p.end());
int n = p.size();
vector<pair<int, int>> ch;
int k = 0;
for(int i = 0; i < n; ch.push_back(p[i++]), k++) {
while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) {
ch.pop_back();
k--;
}
}
for(int i = n - 2, t = k + 1; i >= 0; ch.push_back(p[i--]), k++) {
while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) <= 0) {
ch.pop_back();
k--;
}
}
ch.pop_back();
k--;
return ch;
}
ld Convex_Diameter(const vector<pair<int, int>> &p) {
int n = p.size();
auto d2 = [](pair<int, int> a, pair<int, int> b) -> ll {
ll dx = a.first - b.first, dy = a.second - b.second;
return dx * dx + dy * dy;
};
if(n == 1) return 0;
if(n == 2) return sqrtl((ld)d2(p[0], p[1]));
ll best = 0;
int j = 1;
for(int i = 0; i < n; i++) {
int ni = (i + 1) % n;
auto e = p[ni] - p[i];
// 辺 i→ni から最も遠い頂点まで j を進める(面積が増える間)
while(llabs(cross(e, p[(j + 1) % n] - p[i])) > llabs(cross(e, p[j] - p[i]))) {
j = (j + 1) % n;
}
best = max({best, d2(p[i], p[j]), d2(p[ni], p[j])});
}
return sqrtl((ld)best);
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> p(n);
const int N = 20010;
map<int, int> mp[N];
const int offset = 10000;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
x += offset;
y += offset;
p[i] = {x, y};
mp[x][y] = i;
}
if(n <= 2) {
auto dist = [&](pair<int, int> a, pair<int, int> b) -> ll {
return ((ll)a.first - b.first) * (a.first - b.first) + ((ll)a.second - b.second) * (a.second - b.second);
};
if(n == 0) cout << 1 << endl;
else if(n == 1) cout << 2 << endl;
else {
if(dist(p[0], p[1]) <= 100) {
ld ans = sqrtl(dist(p[0], p[1])) + 2;
cout << fixed << setprecision(15) << ans << endl;
} else {
cout << 2 << endl;
}
}
return;
}
dsu d(n);
for(int i = 0; i < n; i++) {
auto[x, y] = p[i];
for(int j = -10; j <= 10; j++) {
for(int k = 0; k <= 10; k++) {
if(j * j + k * k > 100) break;
if(x + j < N && x + j >= 0 && mp[x + j].count(y + k)) {
d.merge(i, mp[x + j][y + k]);
}
if(x + j < N && x + j >= 0 && mp[x + j].count(y - k)) {
d.merge(i, mp[x + j][y - k]);
}
}
}
}
vector<vector<int>> vec(n);
for(int i = 0; i < n; i++) {
vec[d.leader(i)].push_back(i);
}
ld ans = 0.0;
for(int i = 0; i < n; i++) {
if(vec[i].size() <= 1) continue;
vector<pair<int, int>> p2;
for(auto v : vec[i]) {
p2.push_back(p[v]);
}
if(p2.size() == 2) {
auto[x1, y1] = p2[0];
auto[x2, y2] = p2[1];
ld d = ((ll)x1 - x2) * (x1 - x2) + ((ll)y1 - y2) * (y1 - y2);
d = sqrtl(d);
ans = max(ans, d);
continue;
}
auto res = Convex_Hull(p2);
ld d = Convex_Diameter(res);
ans = max(ans, d);
}
ans += 2;
cout << fixed << setprecision(15) << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while(t--) {
solve();
}
//cout << fixed << setprecision(15) << << endl;
return 0;
}