QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#377512#5505. Great Chaseckiseki#AC ✓551ms50040kbC++202.7kb2024-04-05 14:38:482024-04-05 14:38:49

Judging History

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

  • [2024-04-05 14:38:49]
  • 评测
  • 测评结果:AC
  • 用时:551ms
  • 内存:50040kb
  • [2024-04-05 14:38:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;
using llf = long double;
using P = complex<lld>;

int sgn(lld x) {
  return (x > 0) - (x < 0);
}
lld cross(P a, P b) {
  return imag(conj(a) * b);
}
int ori(P a, P b, P c) {
  return sgn(cross(b - a, c - a));
}

namespace std {
  bool operator<(P a, P b) {
    return make_pair(real(a), imag(a)) < make_pair(real(b), imag(b));
  }
}

vector<P> convex_hull(vector<P> v) {
  sort(all(v));
  if (v[0] == v.back()) return {v[0]};
  int t = 0, s = 1; vector<P> h(v.size() + 1);
  for (int _ = 2; _--; s = t--, reverse(all(v)))
    for (P p : v) {
      while (t > s && ori(p, h[t - 1], h[t - 2]) >= 0) t--;
      h[t++] = p;
    }
  return h.resize(t), h;
}

vector<P> Minkowski(vector<P> A, vector<P> B) {
  const int N = (int)A.size(), M = (int)B.size();
  vector<P> sa(N), sb(M), C(N + M + 1);
  for (int i = 0; i < N; i++) sa[i] = A[(i + 1) % N] - A[i];
  for (int i = 0; i < M; i++) sb[i] = B[(i + 1) % M] - B[i];
  C[0] = A[0] + B[0];
  for (int i = 0, j = 0; i < N || j < M; ) {
    P e = (j >= M || (i < N && cross(sa[i], sb[j]) >= 0))
      ? sa[i++] : sb[j++];
    C[i + j] = e;
  }
  partial_sum(all(C), C.begin());
  C.pop_back();
  return convex_hull(C);
}


llf slope(P z) {
  return imag(z) / llf(real(z));
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int n, v;
    cin >> n >> v;

    vector<P> l, r;
    for (int i = 0; i < n; i++) {
      int64_t p;
      int vi;
      cin >> p >> vi;
      if (p < 0) {
        l.emplace_back(vi, -p);
      } else {
        r.emplace_back(vi, p);
      }
    }

    l = convex_hull(l);
    r = convex_hull(r);

    long double t = 1e18;
    if (l.size() <= 2 || r.size() <= 2) {
      for (auto a : l)
        for (auto b : r) {
          debug(a + b, slope(a + b));
          t = min(t, slope(a + b));
        }
    } else {
      orange(all(l));
      orange(all(r));
      for (auto p : Minkowski(l, r)) {
        debug(p, slope(p));
        t = min(t, slope(p));
      }
    }

    cout << fixed << setprecision(20);
    cout << t * v << '\n';
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

3
4 9
10 2
-7 2
-6 1
7 1
2 8
-1 7
1 6
2 3
-1000000000000 1
1000000000000 1

output:

38.25000000000000000000
1.23076923076923076925
3000000000000.00000000000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 326ms
memory: 4036kb

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

145405766328.34911003708839416504
16414958969.72728119045495986938
5202715639.83518389984965324402
321977234.15632586897118017077
45384199210.22168397158384323120
183885744.76923076923412736505
1708925225.23047235794365406036
89786664971.55794263631105422974
13924365606.28738879505544900894
41297532...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 414ms
memory: 6128kb

input:

93
15435 968117
4196666 184
-5069875 255
-9782648 980
-1978138 176
9333323 764
-4323540 12
-8442049 319
-5371878 137
2881306 10
-4050629 133
-4659099 59
-5189169 320
-2256647 99
-3686648 37
1059255 33
-223142 20
8040933 408
8407764 705
694547 38
-7913614 746
-3573355 132
5919585 189
-3756662 94
-795...

output:

189662921.36363636363239493221
197971181.33333333332848269492
997533531.73762959247687831521
6439673170.66574178496375679970
993821598110.66107785701751708984
22727977326.40266098640859127045
34702455207.51850403100252151489
677770533.92981749866157770157
46631726883.96913323551416397095
5446481867....

result:

ok 93 numbers

Test #4:

score: 0
Accepted
time: 551ms
memory: 50040kb

input:

5
400000 999972
172811492468 106699
171900177092 102097
194121748377 184014
190302947556 172722
183121572232 149212
196566712700 190884
171376795991 99358
522927044000 159597
-129031052077 34395
189422320931 170012
-275879974024 638546
408864707565 98475
-106703244806 368801
192128798630 178213
2915...

output:

519985220219.81177088618278503418
511413015796.76647537946701049805
424240880533.63402035832405090332
518849481155.50391876697540283203
1882496988186.44400000572204589844

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 475ms
memory: 17428kb

input:

38
16668 999947
-3844782803 511
-210897941456 464872
618726004990 714384
-954596898686 225256
96675744 1148
-1515974078 11375
-206213840984 706184
306078847 3947
-474818331950 391451
-616022698917 561244
123378707 1540
-640636592655 406006
459201391325 908506
-733249583 5719
496163273 6238
619876911...

output:

89670748252.97860801219940185547
98630840901.50760696083307266235
29393530999.89432778954505920410
50801000770.95598542317748069763
39668001027.26933134347200393677
467846478226.41137081384658813477
30789914370.57431161217391490936
23151476830.90509843453764915466
51606123416.62582759186625480652
15...

result:

ok 38 numbers