QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#386388 | #5809. Min Perimeter | 0x3b800001 | 5 | 180ms | 17012kb | C++14 | 1.9kb | 2024-04-11 16:09:50 | 2024-04-11 16:09:50 |
Judging History
answer
#include <algorithm>
#include <chrono>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
#include <random>
using ld = double;
int n;
using Point = std::complex<ld>;
Point P[1000007];
int xx[1000007], yy[1000007];
ld diss[1000007][41];
const ld pi = acos(-1);
inline ld dis(Point& lhs, Point& rhs) { return std::abs(lhs - rhs); }
inline ld T(Point& A, Point& B, Point& C) {
return dis(A, B) + dis(B, C) + dis(C, A);
}
inline ld cube(ld s) { return s * s * s; }
inline ld F(Point& Q) { return cube(Q.real()) + cube(Q.imag()); }
void solve() {
std::cin >> n;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ld ans = 1e18;
for (int i = 1; i <= n; ++i) {
std::cin >> xx[i] >> yy[i];
}
for (int f = 0; f < 3; ++f) {
Point r =
std::exp(Point(0, std::uniform_real_distribution<>(-pi, pi)(rng)));
for (int i = 1; i <= n; ++i) {
P[i] = Point(xx[i], yy[i]) * r;
}
std::sort(P + 1, P + n + 1,
[](Point lhs, Point rhs) { return F(lhs) < F(rhs); });
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n && j <= i + 40; ++j) {
diss[i][j - i] = dis(P[i], P[j]);
}
}
for (int i = 1; i <= n - 2; ++i) {
for (int j = i + 1; j <= n && j <= i + 40; ++j) {
if (diss[i][j - i] > ans) {
continue;
}
for (int k = j + 1; k <= n && k <= i + 40; ++k) {
ans = std::min(ans, diss[i][j - i] + diss[j][k - j] + diss[i][k - i]);
}
}
}
}
std::cout << std::fixed << std::setprecision(14) << ans << '\n';
}
int main() {
#ifndef ONLINE_JUDGE
std::freopen("triangle2.in", "r", stdin);
#endif
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
for (int i = 1; i <= t; ++i) {
std::cout << "Case #" << i << ": ";
solve();
}
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 180ms
memory: 17012kb
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.89301220620487 Case #2: 1042.84483496438816 Case #3: 1711142102.79132652282715 Case #4: 90912.29637375113089 Case #5: 3.41421356237304 Case #6: 26.15383034216062 Case #7: 1701.01268109554030 Case #8: 2865438.19199374318123 Case #9: 2020088.33722627954558 Case #10: 1792106.03729183133692 ...
result:
ok correct! (15 test cases)
Subtask #2:
score: 0
Time Limit Exceeded
Test #2:
score: 0
Time Limit Exceeded
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 ...