QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#221587#5505. Great Chaseucup-team859#AC ✓953ms19704kbC++232.1kb2023-10-21 13:53:382023-10-21 13:53:39

Judging History

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

  • [2023-10-21 13:53:39]
  • 评测
  • 测评结果:AC
  • 用时:953ms
  • 内存:19704kb
  • [2023-10-21 13:53:38]
  • 提交

answer

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

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

void solve() {
  int n, v;
  cin >> n >> v;

  vector<pair<ll, ll>> al, ar;
  for (int i = 1; i <= n; ++i) {
    ll x, y;
    cin >> x >> y;
    if (x < 0)
      al.push_back({y, x});
    else
      ar.push_back({-y, x});
  }

  long double st = 0, dr = 1e12;
  int steps = 128;
  while (steps--) {
    long double mij = (st + dr) / 2.0;

    long double l = -1e12;
    for (auto it : al)
      l = max(l, it.first * mij + it.second);

    long double r = 1e12;
    for (auto it : ar)
      r = min(r, it.first * mij + it.second);

    //cout << l << " " << r << " " << mij << endl;
    if (l > r)
      dr = mij;
    else
      st = mij;
  }

  cout << fixed << setprecision(20) << dr * v << endl;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}

详细

Test #1:

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

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.25000000000000000347
1.23076923076923076925
3000000000000.00000000000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 808ms
memory: 3868kb

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.34911005198955535889
16414958969.72728119231760501862
5202715639.83518390031531453133
321977234.15632586897118017077
45384199210.22168397158384323120
183885744.76923076924867928028
1708925225.23047235806006938219
89786664971.55794264376163482666
13924365606.28738879505544900894
41297532...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 950ms
memory: 4448kb

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.36363636364694684744
197971181.33333333334303461015
997533531.73762959247687831521
6439673170.66574178496375679970
993821598110.66107785701751708984
22727977326.40266098827123641968
34702455207.51850403100252151489
677770533.92981749871978536248
46631726883.96913323551416397095
5446481867....

result:

ok 93 numbers

Test #4:

score: 0
Accepted
time: 953ms
memory: 19704kb

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.81177091598510742188
511413015796.76647537946701049805
424240880533.63402038812637329102
518849481155.50391879677772521973
1882496988186.44400000572204589844

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 946ms
memory: 8804kb

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.97860801964998245239
98630840901.50760696083307266235
29393530999.89432778954505920410
50801000770.95598542317748069763
39668001027.26933134719729423523
467846478226.41137084364891052246
30789914370.57431161403656005859
23151476830.90509843453764915466
51606123416.62582759186625480652
15...

result:

ok 38 numbers