結果
問題 | No.96 圏外です。 |
ユーザー | fumiphys |
提出日時 | 2019-09-05 01:04:50 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,825 ms / 5,000 ms |
コード長 | 13,023 bytes |
コンパイル時間 | 2,406 ms |
コンパイル使用メモリ | 199,596 KB |
実行使用メモリ | 19,840 KB |
最終ジャッジ日時 | 2024-06-09 15:45:07 |
合計ジャッジ時間 | 24,971 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,400 KB |
testcase_01 | AC | 3 ms
6,400 KB |
testcase_02 | AC | 3 ms
6,656 KB |
testcase_03 | AC | 3 ms
6,272 KB |
testcase_04 | AC | 19 ms
6,784 KB |
testcase_05 | AC | 33 ms
6,948 KB |
testcase_06 | AC | 56 ms
7,268 KB |
testcase_07 | AC | 92 ms
7,680 KB |
testcase_08 | AC | 132 ms
8,064 KB |
testcase_09 | AC | 188 ms
8,744 KB |
testcase_10 | AC | 273 ms
9,344 KB |
testcase_11 | AC | 350 ms
10,240 KB |
testcase_12 | AC | 435 ms
11,392 KB |
testcase_13 | AC | 630 ms
12,032 KB |
testcase_14 | AC | 762 ms
13,952 KB |
testcase_15 | AC | 1,015 ms
14,720 KB |
testcase_16 | AC | 1,198 ms
17,012 KB |
testcase_17 | AC | 1,339 ms
19,840 KB |
testcase_18 | AC | 1,504 ms
19,200 KB |
testcase_19 | AC | 1,486 ms
19,072 KB |
testcase_20 | AC | 1,320 ms
17,984 KB |
testcase_21 | AC | 938 ms
17,108 KB |
testcase_22 | AC | 3,825 ms
18,872 KB |
testcase_23 | AC | 2,596 ms
18,864 KB |
testcase_24 | AC | 4 ms
6,528 KB |
testcase_25 | AC | 889 ms
15,872 KB |
testcase_26 | AC | 1,230 ms
18,536 KB |
testcase_27 | AC | 1,013 ms
16,768 KB |
ソースコード
// includes #include <bits/stdc++.h> using namespace std; // macros #define pb emplace_back #define mk make_pair #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr) #define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) #define bit(n) (1LL<<(n)) // functions template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;} template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;} template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << p.first << " " << p.second; return os;} template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} // types using ll = long long int; using P = pair<int, int>; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1000000007; //const int dx[4] = {-1, 0, 1, 0}; //const int dy[4] = {0, -1, 0, 1}; // io struct fast_io{ fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);} } fast_io_; typedef struct UnionFind_ { vector<int> par; vector<int> rank_; UnionFind_(){} explicit UnionFind_(int n): rank_(n, 0) { par.resize(n); for(int i = 0; i < n; i++)par[i] = i; } int find(int x) { if(par[x] == x)return x; else return par[x] = find(par[x]); } bool same(int x, int y) { if(find(x) == find(y))return true; else return false; } bool unite(int x, int y){ int xp = find(x); int yp = find(y); if(xp == yp)return false; if(rank_[xp] > rank_[yp])par[yp] = xp; else if(rank_[xp] < rank_[yp])par[xp] = yp; else { par[yp] = xp; rank_[xp]++; } return true; } } UnionFind; struct point2d{ double x, y; point2d(){} point2d(double x, double y): x(x), y(y){} point2d operator+(const point2d &r) const{ return point2d(x + r.x, y + r.y); } point2d operator-(const point2d &r) const{ return point2d(x - r.x, y - r.y); } point2d& operator+=(const point2d &r){ *this = *this + r; return *this; } point2d& operator-=(const point2d &r){ *this = *this - r; return *this; } bool operator==(const point2d &r) const{ return abs(x - r.x) < EPS && abs(y - r.y) < EPS; } bool operator!=(const point2d &r) const{ return !(*this == r); } bool operator<(const point2d &r) const{ if(abs(x - r.x) >= EPS)return x < r.x; return y < r.y; } }; point2d operator*(double x, const point2d &p){ return point2d(x * p.x, x * p.y); } point2d operator/(const point2d &p, double x){ return point2d(p.x / x, p.y / x); } double norm(const point2d &a){ return sqrt(a.x * a.x + a.y * a.y); } double dis(const point2d &a, const point2d &b){ point2d c = a - b; return norm(c); } double inner_product(const point2d &a, const point2d &b){ return a.x * b.x + a.y * b.y; } double outer_product(const point2d &a, const point2d &b){ return a.x * b.y - a.y * b.x; } double cosine(const point2d &a, const point2d &b){ return inner_product(a, b) / norm(a) / norm(b); } double cross(const point2d &o, const point2d &a, const point2d &b){ return outer_product(a - o, b - o); } vector<point2d> convex_hull(vector<point2d> &vec){ int n = vec.size(), k = 0; if(n < 3)return vec; vector<point2d> ch(2 * n); sort(vec.begin(), vec.end()); // lower for(int i = 0; i < n; i++){ while(k >= 2 && cross(ch[k-2], ch[k-1], vec[i]) <= 0.)k--; ch[k++] = vec[i]; } // upper for(int i = n - 1, t = k + 1; i > 0; i--){ while(k >= t && cross(ch[k-2], ch[k-1], vec[i-1]) <= 0.)k--; ch[k++] = vec[i-1]; } ch.resize(k-1); return ch; } struct point3d{ double x, y, z; point3d(){} point3d(double x, double y, double z): x(x), y(y), z(z){} point3d operator+(const point3d &r) const{ return point3d(x + r.x, y + r.y, z + r.z); } point3d operator-(const point3d &r) const{ return point3d(x - r.x, y - r.y, z - r.z); } point3d& operator+=(const point3d &r){ *this = *this + r; return *this; } point3d& operator-=(const point3d &r){ *this = *this - r; return *this; } bool operator==(const point3d &r) const{ return abs(x - r.x) < EPS && abs(y - r.y) < EPS && abs(z - r.z) < EPS; } bool operator!=(const point3d &r) const{ return !(*this == r); } bool operator<(const point3d &r) const{ if(abs(x - r.x) >= EPS)return x < r.x; if(abs(y - r.y) >= EPS)return y < r.y; return z < r.z; } }; point3d operator*(double x, const point3d &p){ return point3d(x * p.x, x * p.y, x * p.z); } point3d operator/(const point3d &p, double x){ return point3d(p.x / x, p.y / x, p.z / x); } double norm(const point3d &a){ return sqrt(a.x * a.x + a.y * a.y + a.z * a.z); } double dis(const point3d &a, const point3d &b){ point3d c = a - b; return norm(c); } double inner_product(const point3d &a, const point3d &b){ return a.x * b.x + a.y * b.y + a.z * b.z; } point3d outer_product(const point3d &a, const point3d &b){ return point3d(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x); } double cosine(const point3d &a, const point3d &b){ return inner_product(a, b) / norm(a) / norm(b); } struct plane3d{ double a, b, c, d; double norm = 1.; plane3d(){} plane3d(double a, double b, double c, double d): a(a), b(b), c(c), d(d){ build(); } plane3d(const point3d pa, const point3d pb, const point3d pc){ point3d re = outer_product(pb - pa, pc - pa); a = re.x, b = re.y, c = re.z; d = - (a * pa.x + b * pa.y + c * pa.z); build(); } void build(){ norm = sqrt(a * a + b * b + c * c); } double dis(point3d p){ return abs(a * p.x + b * p.y + c * p.z + d) / norm; } double val(const point3d &p){ return a * p.x + b * p.y + c * p.z + d; } }; point2d projection(const point2d &p, const point2d &p1, const point2d &p2){ point2d p2p1 = p2 - p1, pp1 = p - p1; if(abs(inner_product(p2p1, pp1)) < EPS)return p1; double cosi = cosine(p2p1, pp1); return p1 + (dis(p, p1) * cosi / norm(p2 - p1)) * (p2 - p1); } point2d reflection(const point2d &p, const point2d &p1, const point2d &p2){ point2d pr = projection(p, p1, p2); return p + 2. * (pr - p); } struct plane2d{ double a, b, c; double norm; plane2d(){} plane2d(double a, double b, double c): a(a), b(b), c(c){} plane2d(const point2d &p, const point2d &q){ point2d l = p - q; a = l.y, b = - l.x; c = - a * p.x - b * p.y; build(); } void build(){ norm = sqrt(a * a + b * b); } double dis(const point2d &p){ return abs(a * p.x + b * p.y + c) / norm; } double val(const point2d &p){ return a * p.x + b * p.y + c; } }; bool parallel(const plane2d &p, const plane2d &q){ return abs(p.a * q.b - p.b * q.a) < EPS; } bool orthogonal(const plane2d &p, const plane2d &q){ return abs(p.a * q.a + p.b * q.b) < EPS; } bool intersection(const point2d &p1, const point2d &p2, const point2d &p3, const point2d &p4){ plane2d pl1(p1, p2), pl2(p3, p4); if(abs(pl1.val(p3)) < EPS && min(p1.x, p2.x) <= p3.x && p3.x <= max(p1.x, p2.x) && min(p1.y, p2.y) <= p3.y && p3.y <= max(p1.y, p2.y))return true; if(abs(pl1.val(p4)) < EPS && min(p1.x, p2.x) <= p4.x && p4.x <= max(p1.x, p2.x) && min(p1.y, p2.y) <= p4.y && p4.y <= max(p1.y, p2.y))return true; if(abs(pl2.val(p1)) < EPS && min(p3.x, p4.x) <= p1.x && p1.x <= max(p3.x, p4.x) && min(p3.y, p4.y) <= p1.y && p1.y <= max(p3.y, p4.y))return true; if(abs(pl2.val(p2)) < EPS && min(p3.x, p4.x) <= p2.x && p2.x <= max(p3.x, p4.x) && min(p3.y, p4.y) <= p2.y && p2.y <= max(p3.y, p4.y))return true; return pl1.val(p3) * pl1.val(p4) <= - EPS && pl2.val(p1) * pl2.val(p2) <= - EPS; } double closest_pair(vector<point2d> &a, int l, int r){ double d = numeric_limits<double>::max(); if(r - l == 1)return d; int m = (l + r) / 2; double x = a[m].x; d = min(closest_pair(a, l, m), closest_pair(a, m, r)); inplace_merge(a.begin() + l, a.begin() + m, a.begin() + r, [](const point2d &u, const point2d &v){ return u.y < v.y; }); vector<point2d> v; for(int i = l; i < r; i++){ if(abs(x - a[i].x) >= d)continue; for(int j = 0; j < v.size(); j++){ double dx = a[i].x - v[v.size()-j-1].x; double dy = a[i].y - v[v.size()-j-1].y; if(dy >= d)break; d = min(d, sqrt(dx * dx + dy * dy)); } v.push_back(a[i]); } return d; } double closest_pair(vector<point2d> &a){ sort(a.begin(), a.end(), [](const point2d &u, const point2d &v){ if(u.x != v.x)return u.x < v.x; return u.y < v.y; }); return closest_pair(a, 0, int(a.size())); } // begin library circle here // usage of this library: circle c(point2d(x, y), r); // usage of this library: circle_crossing_state(c1, c2); struct circle{ point2d c; double r; circle(){} circle(point2d c, double r): c(c), r(r){} }; enum circle_crossing_state{ NOTCROSS = 4, CIRCUMSCRIBE = 3, INTERSECT = 2, INSCRIBED = 1, INCLUDED = 0, }; circle_crossing_state circle_crossing(const circle &a, const circle &b){ double d = dis(a.c, b.c); cout << setprecision(20); if(d > a.r + b.r + EPS)return NOTCROSS; if(abs(d - (a.r + b.r)) < EPS)return CIRCUMSCRIBE; if(abs(d - abs(a.r - b.r)) < EPS)return INSCRIBED; if(d + EPS < abs(a.r - b.r))return INCLUDED; return INTERSECT; } // end library // begin library square_test here // usage of this library: square_test(x, y); // for int or long long template <typename T> bool square_test(const vector<T> &x, const vector<T> &y){ assert(x.size() == 4); assert(y.size() == 4); vector<T> v; for(size_t i = 0; i < x.size(); i++){ for(size_t j = i + 1; j < y.size(); j++){ T d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); v.push_back(d); } } sort(v.begin(), v.end()); T b = v[0]; if(b == 0)return false; for(int i = 1; i < 4; i++){ if(v[i] != b)return false; } for(int i = 4; i < 6; i++){ if(v[i] != b * 2)return false; } return true; } // end library vector<int> v[120010]; int main(int argc, char const* argv[]) { int n; cin >> n; if(n == 0){ cout << 1 << endl; return 0; } vector<ll> x(n), y(n); rep(i, n)cin >> x[i] >> y[i]; map<P, int> mp; // rep(i, n)mp[mk(x[i], y[i])] = i; UnionFind uf(n); rep(i, n){ for(int dx = -10; dx <= 10; dx++){ for(int dy = -10; dy <= 10; dy++){ ll X = x[i] + dx; ll Y = y[i] + dy; ll di = dx * dx + dy * dy; if(di <= 100 && mp.find(mk(X, Y)) != mp.end()){ int idx = mp[mk(X, Y)]; uf.unite(i, idx); } } } mp[mk(x[i], y[i])] = i; } double res = 2.; rep(i, n)v[uf.find(i)].pb(i); rep(i, n){ if(sz(v[i]) == 0)continue; vector<point2d> vp(sz(v[i])); rep(j, sz(v[i]))vp[j] = point2d(x[v[i][j]], y[v[i][j]]); auto ch = convex_hull(vp); int l = 0; rep(j, sz(ch)){ double prev = 0.; FOR(k, max(l, j + 1), sz(ch)){ double di = dis(ch[k], ch[j]); if(res < di + 2.){ res = di + 2.; l = k; } if(di < prev)break; prev = di; } } } cout << res << endl; return 0; }