結果

問題 No.96 圏外です。
ユーザー t98slidert98slider
提出日時 2022-06-01 23:20:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,425 ms / 5,000 ms
コード長 4,759 bytes
コンパイル時間 2,273 ms
コンパイル使用メモリ 186,236 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-09-21 01:46:22
合計ジャッジ時間 22,175 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 21 ms
5,376 KB
testcase_05 AC 37 ms
5,376 KB
testcase_06 AC 61 ms
5,376 KB
testcase_07 AC 95 ms
5,376 KB
testcase_08 AC 138 ms
5,376 KB
testcase_09 AC 191 ms
5,376 KB
testcase_10 AC 274 ms
5,376 KB
testcase_11 AC 352 ms
5,632 KB
testcase_12 AC 436 ms
6,400 KB
testcase_13 AC 611 ms
6,656 KB
testcase_14 AC 738 ms
7,936 KB
testcase_15 AC 954 ms
7,808 KB
testcase_16 AC 1,117 ms
9,856 KB
testcase_17 AC 1,280 ms
11,776 KB
testcase_18 AC 1,397 ms
11,008 KB
testcase_19 AC 1,398 ms
11,136 KB
testcase_20 AC 1,401 ms
9,216 KB
testcase_21 AC 988 ms
8,880 KB
testcase_22 AC 1,378 ms
9,544 KB
testcase_23 AC 1,425 ms
9,636 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 864 ms
9,216 KB
testcase_26 AC 1,151 ms
11,072 KB
testcase_27 AC 979 ms
9,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
 
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

vector<pair<int,int>> Totsuho(vector<pair<int,int>> &pos){
    int n=pos.size(),n1,n2;
    sort(pos.begin(),pos.end());
    vector<pair<int,int>> res1={pos[0],pos[1]},res2={pos[0],pos[1]};
    auto cross=[&](pair<int,int> a,pair<int,int> b){
        return (long long)a.first*b.second-(long long)a.second*b.first;
    };
    auto sub=[&](pair<int,int> a,pair<int,int> b){
        return make_pair(a.first-b.first,a.second-b.second);
    };
    for(int i=2;i<n;i++){
        n1=res1.size(),n2=res2.size();
        while(n1>=2&&cross(sub(res1[n1-1],res1[n1-2]),sub(pos[i],res1[n1-1]))<=0){
            res1.pop_back();
            n1--;
        }
        while(n2>=2&&cross(sub(res2[n2-1],res2[n2-2]),sub(pos[i],res2[n2-1]))>=0){
            res2.pop_back();
            n2--;
        }
        res1.push_back(pos[i]);
        res2.push_back(pos[i]);
    }
    for (int i=res2.size()-2;i>=1;i--)res1.push_back(res2[i]);
    return res1;
}

double Calipers(vector<pair<int,int>> &tot){
    int n = tot.size();
    auto dist = [&](int i, int j){
        long long dy = tot[i].first - tot[j].first;
        long long dx = tot[i].second - tot[j].second;
        return dy * dy + dx * dx;
    };
    auto cross=[&](pair<int,int> a,pair<int,int> b){
        return (long long)a.first*b.second-(long long)a.second*b.first;
    };
    auto sub=[&](pair<int,int> a,pair<int,int> b){
        return make_pair(a.first-b.first,a.second-b.second);
    };
    if(n == 1){
        return 0;
    }
    if(n == 2){
        return sqrt(dist(0, 1));
    }
    double ans = 0;
    int i = 0, j = 0;
    for(int k = 0; k < n; k++){
        if(tot[k].first < tot[i].first)i = k;
        if(tot[k].first > tot[j].first)j = k;
    }
    int si = i, sj = j;
    int cnt = 0;
    while(i != sj || j != sj){
        cnt ++;
        ans = max(ans, sqrt(dist(i, j)));
        int i2 = i + 1 == n ? 0 : i + 1, j2 = j + 1 == n ? 0 : j + 1;
        if(cross(sub(tot[i2],tot[i]),sub(tot[j2],tot[j])) < 0){
            i = i2;
        }else{
            j = j2;
        }
        if(cnt >= 2*n)break;
    }
    return ans;
}

int main(){
    int n, y, x;
    cin >> n;
    vector<pair<int,int>> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    dsu uf(n);
    for(int i = 0; i < n; i++){
        tie(y, x) = a[i];
        for(int dy = -10; dy <= 10; dy++){
            for(int dx = -10; dx <= 10; dx++){
                if(dy * dy + dx * dx > 100)continue;
                auto p = make_pair(y + dy, x + dx);
                int j = lower_bound(a.begin(), a.end(), p) - a.begin();
                if(j < n && a[j] == p){
                    uf.merge(i, j);
                }
            }
        }
    }
    double ans = 1 + (n != 0);
    auto G = uf.groups();
    for(auto &&b:G){
        if(b.size() == 1)continue;
        vector<pair<int,int>> c;
        for(auto i:b)c.push_back(a[i]);
        auto tot = Totsuho(c);
        ans = max(ans, 2 + Calipers(tot));
    }
    printf("%.15lf\n",ans);
}
0