QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386388#5809. Min Perimeter0x3b8000015 180ms17012kbC++141.9kb2024-04-11 16:09:502024-04-11 16:09:50

Judging History

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

  • [2024-04-11 16:09:50]
  • 评测
  • 测评结果:5
  • 用时:180ms
  • 内存:17012kb
  • [2024-04-11 16:09:50]
  • 提交

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
...

output:


result: