oj.uz

답안 #56137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56137 2018-07-10T05:36:33 Z 강태규(#1579) Mobile (BOI12_mobile) C++11
100 / 100
 474 ms 24188 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e9 + 7;
int n, l, m = -1;
int x[1000000];
int y[1000000];

llong sq(int x) {
    return (llong)x * x;
}

struct line {
    llong m, b;
    ld get(ld x) const {
        return m * x + b;
    }
    ld inter(line x) const {
        return (ld)(b - x.b) / (x.m - m);
    }
} st[1000000];

int tp = 0;

int main() {
    scanf("%d%d", &n, &l);
    for (int i = 0, pr = inf; i < n; ++i) {
        int xs, ys;
        scanf("%d%d", &xs, &ys);
        if (ys < 0) ys = -ys;
        if (xs != pr) {
            x[++m] = xs;
            y[m] = ys;
            pr = xs;
        }
        else {
            y[m] = min(y[m], ys);
        }
    }
    for (int i = 0; i <= m; ++i) {
        line l = { -2 * x[i], sq(x[i]) + sq(y[i]) };
        while (tp > 1 && st[tp - 1].inter(l) < st[tp - 2].inter(st[tp - 1]))
            --tp;
        st[tp++] = l;
    }
    ld ans = 0;
    for (int i = 1; i < tp; ++i) {
        ld x = st[i - 1].inter(st[i]);
        if (0 <= x && x <= l) ans = max(ans, x * x + st[i].get(x));
    }
    ld ans1 = 1e20, ans2 = 1e20;
    for (int i = 0; i < tp; ++i) {
        ans1 = min(ans1, st[i].get(0));
        ans2 = min(ans2, sq(l) + st[i].get(l));
    }
    ans = max({ ans, ans1, ans2 });
    cout.precision(20);
    cout << sqrt(ans) << '\n';
	return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~
mobile.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &xs, &ys);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 4 ms 656 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 656 KB Output is correct
2 Correct 6 ms 656 KB Output is correct
3 Correct 5 ms 656 KB Output is correct
4 Correct 3 ms 664 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 5 ms 748 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1260 KB Output is correct
2 Correct 24 ms 1260 KB Output is correct
3 Correct 16 ms 1260 KB Output is correct
4 Correct 29 ms 1260 KB Output is correct
5 Correct 14 ms 1260 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 1260 KB Output is correct
2 Correct 25 ms 1260 KB Output is correct
3 Correct 38 ms 1260 KB Output is correct
4 Correct 32 ms 1260 KB Output is correct
5 Correct 36 ms 1280 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 2688 KB Output is correct
2 Correct 23 ms 2688 KB Output is correct
3 Correct 22 ms 2688 KB Output is correct
4 Correct 37 ms 2688 KB Output is correct
5 Correct 23 ms 2688 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 2688 KB Output is correct
2 Correct 39 ms 2688 KB Output is correct
3 Correct 22 ms 2688 KB Output is correct
4 Correct 46 ms 2688 KB Output is correct
5 Correct 32 ms 2688 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2688 KB Output is correct
2 Correct 30 ms 2688 KB Output is correct
3 Correct 25 ms 2688 KB Output is correct
4 Correct 42 ms 2688 KB Output is correct
5 Correct 33 ms 2688 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 12284 KB Output is correct
2 Correct 128 ms 12284 KB Output is correct
3 Correct 116 ms 12284 KB Output is correct
4 Correct 193 ms 12284 KB Output is correct
5 Correct 141 ms 12284 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 12284 KB Output is correct
2 Correct 161 ms 12284 KB Output is correct
3 Correct 142 ms 12284 KB Output is correct
4 Correct 211 ms 12284 KB Output is correct
5 Correct 201 ms 12284 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 14716 KB Output is correct
2 Correct 153 ms 14716 KB Output is correct
3 Correct 233 ms 14716 KB Output is correct
4 Correct 232 ms 14716 KB Output is correct
5 Correct 186 ms 14716 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 14716 KB Output is correct
2 Correct 198 ms 14716 KB Output is correct
3 Correct 195 ms 14716 KB Output is correct
4 Correct 249 ms 14716 KB Output is correct
5 Correct 213 ms 14716 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 17012 KB Output is correct
2 Correct 193 ms 17012 KB Output is correct
3 Correct 172 ms 17012 KB Output is correct
4 Correct 255 ms 17012 KB Output is correct
5 Correct 279 ms 17012 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 17012 KB Output is correct
2 Correct 270 ms 17012 KB Output is correct
3 Correct 203 ms 17012 KB Output is correct
4 Correct 255 ms 17012 KB Output is correct
5 Correct 277 ms 17012 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 19300 KB Output is correct
2 Correct 216 ms 19300 KB Output is correct
3 Correct 208 ms 19300 KB Output is correct
4 Correct 334 ms 19300 KB Output is correct
5 Correct 282 ms 19300 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 19300 KB Output is correct
2 Correct 235 ms 19300 KB Output is correct
3 Correct 238 ms 19300 KB Output is correct
4 Correct 303 ms 19300 KB Output is correct
5 Correct 284 ms 19300 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 474 ms 24188 KB Output is correct
2 Correct 272 ms 24188 KB Output is correct
3 Correct 286 ms 24188 KB Output is correct
4 Correct 356 ms 24188 KB Output is correct
5 Correct 277 ms 24188 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 24188 KB Output is correct
2 Correct 365 ms 24188 KB Output is correct
3 Correct 299 ms 24188 KB Output is correct
4 Correct 360 ms 24188 KB Output is correct
5 Correct 317 ms 24188 KB Output is correct