QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385253#5809. Min Perimeterzjy00015 9073ms32844kbC++172.4kb2024-04-10 16:59:152024-04-10 16:59:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 16:59:15]
  • 评测
  • 测评结果:5
  • 用时:9073ms
  • 内存:32844kb
  • [2024-04-10 16:59:15]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e6+5;
const ldb INF=1e10;
int n;ldb ans,D[N];pair<int,int>A[N];
inline ldb dist(const int&x,const int&y){
    const auto [xx,xy]=A[x];const auto [yx,yy]=A[y];
    return sqrtl(1ll*(xx-yx)*(xx-yx)+1ll*(xy-yy)*(xy-yy));
}
inline bool cmp(const pair<int,int>&x,const pair<int,int>&y){
    return x.second<y.second;
}
inline void solve(int l,int r){
    if(r-l<2){
        if(l<r&&!cmp(A[l],A[r]))swap(A[l],A[r]);
        return;
    }
    const int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);
    const int lx=max_element(A+l,A+mid+1)->first;
    const int rx=min_element(A+mid+1,A+r+1)->first;
    vector<int>S;
    for(int i=l,lp=mid+1,rp=mid+1;i<=mid;++i)
        if(rx-A[i].first<ans){
            for(;rp<=r&&A[rp].second-A[i].second<ans;++rp)
                if(A[rp].first-lx<ans)S.emplace_back(rp);
            for(;lp<rp&&A[i].second-A[lp].second>=ans;++lp);
            vector<int>T;T.reserve(10);
            for(auto j:S)if(j>=lp&&A[j].first-lx<ans)
                T.emplace_back(j),D[j]=dist(i,j);
            S=move(T);
            for(auto j:S)if(D[j]<ans)for(auto k:S)
                if(k<j)if(D[k]<ans)ans=min(ans,(D[j]+D[k]+dist(j,k))/2);
                else break;
        }
    S.clear();
    for(int i=mid+1,lp=l,rp=l;i<=r;++i)
        if(A[i].first-lx<ans){
            for(;rp<=mid&&A[rp].second-A[i].second<ans;++rp)
                if(rx-A[rp].first<ans)S.emplace_back(rp);
            for(;lp<rp&&A[i].second-A[lp].second>=ans;++lp);
            vector<int>T;T.reserve(10);
            for(auto j:S)if(j>=lp&&rx-A[j].first<ans)
                T.emplace_back(j),D[j]=dist(i,j);
            S=move(T);
            for(auto j:S)if(D[j]<ans)for(auto k:S)
                if(k<j)if(D[k]<ans)ans=min(ans,(D[j]+D[k]+dist(j,k))/2);
                else break;
        }
    inplace_merge(A+l,A+mid+1,A+r+1,cmp);
}
inline void MAIN(){
    cin>>n,ans=INF;
    for(int i=1;i<=n;++i)
        cin>>A[i].first>>A[i].second;
    sort(A+1,A+n+1),solve(1,n);
    cout<<fixed<<setprecision(12)<<ans*2<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t=1;cin>>t;for(int _=1;t--;++_)
        cout<<"Case #"<<_<<": ",MAIN();
    return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 61ms
memory: 4200kb

input:

15
3
2 6
7 0
3 0
3
713 269
371 79
455 421
3
91983245 637281504
756917015 312173515
869576338 436726680
10000
14761642 78236002
9047458 47951098
5238002 27761162
476182 2523742
1428546 7571226
26190010 138805810
21904372 116092132
18094916 95902196
43332562 229660522
55237112 292754072
52380020 27761...

output:

Case #1: 17.893012206205
Case #2: 1042.844834964388
Case #3: 1711142102.791327107698
Case #4: 90912.296374032924
Case #5: 3.414213562373
Case #6: 26.153830342164
Case #7: 1701.012681095617
Case #8: 2865438.191993871100
Case #9: 2020088.337226319682
Case #10: 1792106.037292071139
Case #11: 2019352.54...

result:

ok correct! (15 test cases)

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 9073ms
memory: 32844kb

input:

15
3
501691275 344354353
167768963 536043860
249445040 557426549
4
1000000000 0
0 0
1000000000 1000000000
0 1000000000
1000000
138925776 669369648
61257680 295150640
170762328 822763944
55483472 267329456
97736936 470914328
84041848 404928904
18463588 88960924
124429360 599523280
95066048 458045504
...

output:

Case #1: 799653579.133089741750
Case #2: 3414213562.373095048824
Case #3: 866.071590574359
Case #4: 62459.895369637148
Case #5: 59141.918358931781
Case #6: 898200.341132124273
Case #7: 1707097.263416094579
Case #8: 1693.217785077377
Case #9: 1687.288442046181
Case #10: 6808.003068300724
Case #11: 19...

result:

wrong answer read 1693.217785077377 but expected 1686.226798258136 (test case 8)