QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385253 | #5809. Min Perimeter | zjy0001 | 5 | 9073ms | 32844kb | C++17 | 2.4kb | 2024-04-10 16:59:15 | 2024-04-10 16:59:15 |
Judging History
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)