oj.uz

Submission #970993

# Submission time Handle Problem Language Result Execution time Memory
970993 2024-04-27T18:03:45 Z hgmhc Mobile (BOI12_mobile) C++17
100 / 100
 393 ms 35448 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) (x = max(x,y))
#define mup(x,y) (x = min(x,y))
#define fi first
#define se second
#define pb push_back
#define dbg(...) fprintf(stderr,__VA_ARGS__)

#pragma region Geometry
#define pt complex<coord_t>
#define TCT template <typename coord_t>

using ld = long double;
const ld PI = acos(-1.0L), EPS = 1e-9;
using Zpt = complex<ll>; using Rpt = complex<ld>;
#define X real()
#define Y imag()

TCT inline coord_t dot(pt u, pt v) { return (conj(u)*v).X; }
TCT inline coord_t cross(pt u, pt v) { return (conj(u)*v).Y; }
TCT inline coord_t orient(pt a, pt b, pt c) { return cross(b-a,c-b); }
TCT inline coord_t abs2(pt u) { return dot(u,u); }
TCT inline      ld abs1(pt u) { return sqrt(ld(abs2(u))); }

TCT istream &operator >> (istream &is, pt &p) {
    coord_t x, y; is >> x >> y; p = {x,y}; return is;
}
namespace std {
    bool operator < (const Zpt &u, const Zpt &v) {
        return u.X == v.X ? u.Y < v.Y : u.X < v.X;
    }
}

#undef pt
#undef TCT
#pragma endregion

using pt = Zpt;

const int N = 1e6+3;
int n;
double l;
pt p[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> l;
    rep(i,1,n) cin >> p[i];
    
    auto covered = [](double x) {
        double ptr = 0;
        rep(i,1,n) {
            double dif = sqrt(x*x-p[i].Y*p[i].Y);
            if (p[i].X-dif < ptr+1e-9) Mup(ptr, p[i].X+dif);
        }
        return l < ptr+1e-9;
    };
    
    double a=0, b=1e10, m;
    while (b-a > 1e-3) {
        m = (a+b)/2;
        if (covered(m)) b = m;
        else a = m;
    }
    cout << fixed << setprecision(6) << m;
}

Compilation message

mobile.cpp:14: warning: ignoring '#pragma region Geometry' [-Wunknown-pragmas]
   14 | #pragma region Geometry
      | 
mobile.cpp:41: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   41 | #pragma endregion
      |

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 6 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3416 KB Output is correct
2 Correct 31 ms 3748 KB Output is correct
3 Correct 18 ms 3164 KB Output is correct
4 Correct 41 ms 3800 KB Output is correct
5 Correct 22 ms 3080 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3416 KB Output is correct
2 Correct 22 ms 3420 KB Output is correct
3 Correct 25 ms 3928 KB Output is correct
4 Correct 32 ms 3672 KB Output is correct
5 Correct 32 ms 3928 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3352 KB Output is correct
2 Correct 26 ms 3836 KB Output is correct
3 Correct 23 ms 3580 KB Output is correct
4 Correct 37 ms 4448 KB Output is correct
5 Correct 28 ms 3616 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4068 KB Output is correct
2 Correct 27 ms 3924 KB Output is correct
3 Correct 27 ms 3672 KB Output is correct
4 Correct 42 ms 4600 KB Output is correct
5 Correct 31 ms 3928 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4188 KB Output is correct
2 Correct 27 ms 3960 KB Output is correct
3 Correct 26 ms 3700 KB Output is correct
4 Correct 39 ms 4444 KB Output is correct
5 Correct 30 ms 3928 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12884 KB Output is correct
2 Correct 133 ms 16540 KB Output is correct
3 Correct 133 ms 16044 KB Output is correct
4 Correct 179 ms 18284 KB Output is correct
5 Correct 155 ms 15644 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 17028 KB Output is correct
2 Correct 202 ms 15200 KB Output is correct
3 Correct 132 ms 14572 KB Output is correct
4 Correct 195 ms 18004 KB Output is correct
5 Correct 181 ms 15956 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 16048 KB Output is correct
2 Correct 157 ms 20036 KB Output is correct
3 Correct 181 ms 19568 KB Output is correct
4 Correct 216 ms 22612 KB Output is correct
5 Correct 187 ms 18924 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 21084 KB Output is correct
2 Correct 232 ms 18664 KB Output is correct
3 Correct 169 ms 17500 KB Output is correct
4 Correct 213 ms 22352 KB Output is correct
5 Correct 201 ms 19588 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 18924 KB Output is correct
2 Correct 220 ms 23528 KB Output is correct
3 Correct 188 ms 22888 KB Output is correct
4 Correct 253 ms 26448 KB Output is correct
5 Correct 231 ms 22112 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 24404 KB Output is correct
2 Correct 260 ms 21996 KB Output is correct
3 Correct 205 ms 21224 KB Output is correct
4 Correct 240 ms 26196 KB Output is correct
5 Correct 245 ms 23052 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 22096 KB Output is correct
2 Correct 212 ms 27380 KB Output is correct
3 Correct 219 ms 26600 KB Output is correct
4 Correct 301 ms 30608 KB Output is correct
5 Correct 254 ms 25972 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 28160 KB Output is correct
2 Correct 299 ms 25332 KB Output is correct
3 Correct 207 ms 24404 KB Output is correct
4 Correct 277 ms 30196 KB Output is correct
5 Correct 257 ms 26740 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 24696 KB Output is correct
2 Correct 295 ms 31608 KB Output is correct
3 Correct 285 ms 30548 KB Output is correct
4 Correct 347 ms 35264 KB Output is correct
5 Correct 310 ms 29516 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 32492 KB Output is correct
2 Correct 362 ms 29272 KB Output is correct
3 Correct 256 ms 28244 KB Output is correct
4 Correct 393 ms 35448 KB Output is correct
5 Correct 327 ms 30644 KB Output is correct