QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386398#5809. Min Perimeter0x3b8000015 15744ms816820kbC++141.9kb2024-04-11 16:15:242024-04-11 16:15:24

Judging History

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

  • [2024-04-11 16:15:24]
  • 评测
  • 测评结果:5
  • 用时:15744ms
  • 内存:816820kb
  • [2024-04-11 16:15:24]
  • 提交

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][100 + 1];
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 < 1; ++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 + 100; ++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 + 100; ++j) {
        if (diss[i][j - i] > ans) {
          continue;
        }
        for (int k = j + 1; k <= n && k <= i + 100; ++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: 133ms
memory: 18504kb

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.84483496438793
Case #3: 1711142102.79132699966431
Case #4: 90912.29637364402879
Case #5: 3.41421356237307
Case #6: 26.15383034216412
Case #7: 1701.01268109565308
Case #8: 2865438.19199343165383
Case #9: 2020088.33722639037296
Case #10: 1792106.03729193354957
...

result:

ok correct! (15 test cases)

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 15744ms
memory: 816820kb

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.13308978080750
Case #2: 3414213562.37309503555298
Case #3: 866.07159011897943
Case #4: 62459.89536952108028
Case #5: 59141.91835884546890
Case #6: 898200.35246480139904
Case #7: 1707101.20907206367701
Case #8: 1703.58309032487296
Case #9: 1702.08048770483265
Case #10: 6806.6655840...

result:

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