oj.uz

답안 #91790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91790 2018-12-30T02:59:25 Z updown1 Mobile (BOI12_mobile) C++17
12 / 100
 1000 ms 32024 KB 
/*
binary search on the answer
to test a value x, for all the circles come up with ranges of the line that is covered if the circle has a radius x
find the minimum value x s.t. the whole line is covered
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//#define double long double
const int MAXN=1000000;
///500,000,000
int N, L;
pair<double, double> pts[MAXN], rng[MAXN];

bool full(double rr) {
    /// make the ranges
    ffi {
        int x = pts[i].a, y = pts[i].b;
        if (y*y > rr*rr) {rng[i] = mp(0, 0); continue;}
        double a = sqrt((long double)rr*rr-y*y);
        double l = x - a; double r = x + a;
        l = max(l, (double) 0); l = min(l, (double)L);
        r = max(r, (double) 0); r = min(r, (double)L);
        rng[i] = mp(l, r);
    }
    //w<< rr<<e; ffi w<< rng[i].a s rng[i].b<<e;
    /// see if the whole range is covered
    double far = 0;
    ffi {
        if (rng[i].a > far) continue;
        far = max(far, rng[i].b);
    }
    return far >=L;
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> L;
	double a = 2236067978, b = 2236067978;
	ffi {
	    cin >> pts[i].a >> pts[i].b;
	    double x = pts[i].a, y = pts[i].b;
	    double use1 = sqrt((long double)x*x+y*y);
	    double use2 = sqrt((long double)(x-L)*(x-L)+y*y);
	    b = min(b, max(use1, use2));
	    a = min(a, min(use1, use2));
	}
	while (b-a > .001) {
        double mid = (a+b)/2;
        if (full(mid)) b = mid;
        else a = mid;
	}
	w<< fixed << setprecision(6) <<a<<e;
}

Compilation message

mobile.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Incorrect 6 ms 504 KB Output isn't correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Incorrect 6 ms 504 KB Output isn't correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Incorrect 6 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 2808 KB Output is correct
2 Incorrect 65 ms 2888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 2936 KB Output is correct
2 Correct 42 ms 2680 KB Output is correct
3 Incorrect 64 ms 3064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 3192 KB Output is correct
2 Incorrect 73 ms 3192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 3576 KB Output is correct
2 Incorrect 85 ms 3576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 3576 KB Output is correct
2 Incorrect 86 ms 3576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 396 ms 16136 KB Output is correct
2 Incorrect 440 ms 16120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 481 ms 16272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 493 ms 19192 KB Output is correct
2 Incorrect 577 ms 19448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 565 ms 19448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 585 ms 22392 KB Output is correct
2 Incorrect 673 ms 22520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 674 ms 22456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 659 ms 25660 KB Output is correct
2 Incorrect 726 ms 25724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 754 ms 25592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 784 ms 31896 KB Output is correct
2 Incorrect 950 ms 32024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1022 ms 32004 KB Time limit exceeded
2 Halted 0 ms 0 KB -