結果
| 問題 | No.96 圏外です。 |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 16:38:52 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 5,139 bytes |
| 記録 | |
| コンパイル時間 | 3,768 ms |
| コンパイル使用メモリ | 296,008 KB |
| 実行使用メモリ | 9,840 KB |
| 最終ジャッジ日時 | 2026-11-16 16:39:06 |
| 合計ジャッジ時間 | 13,650 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 TLE * 1 -- * 22 |
ソースコード
#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(vector<pair<int, int>> p) {
int n = p.size();
int is = 0, js = 0;
for(int i = 1; i < n; i++) {
if(p[i].second > p[is].second) is = i;
if(p[i].second < p[js].second) js = i;
}
auto dist = [&](pair<int, int> a, pair<int, int> b) -> ld {
ld res = ((ll)a.first - b.first) * (a.first - b.first) + ((ll)a.second - b.second) * (a.second - b.second);
res = sqrtl(res);
return res;
};
ld maxdis = dist(p[is], p[js]);
int maxi, maxj, i, j;
i = maxi = is;
j = maxj = js;
do {
if(cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0) {
j = (j + 1) % n;
} else {
i = (i + 1) % n;
}
if(dist(p[i], p[j]) > maxdis) {
maxdis = dist(p[i], p[j]);
maxi = i, maxj = j;
}
} while(i != is || j != js);
return maxdis;
}
void solve() {
int n;
cin >> n;
vector<pair<int, int>> p(n);
map<pair<int, int>, int> mp;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
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++) {
for(int j = -10; j <= 10; j++) {
for(int k = 0; k <= 10; k++) {
if(j * j + k * k > 100) break;
if(mp.count({p[i].first + j, p[i].second + k})) {
d.merge(i, mp[{p[i].first + j, p[i].second + k}]);
}
if(mp.count({p[i].first + j, p[i].second - k})) {
d.merge(i, mp[{p[i].first + j, p[i].second - 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() == 0) continue;
vector<pair<int, int>> p2;
for(auto v : vec[i]) {
p2.push_back(p[v]);
}
auto res = Convex_Hull(p2);
ld d = Convex_Diameter(p2);
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;
}