oj.uz

Submission #133183

# Submission time Handle Problem Language Result Execution time Memory
133183 2019-07-20T08:47:06 Z sealnot123 Mobile (BOI12_mobile) C++14
15 / 100
 352 ms 32728 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1000007;
PLL tower[N];

bool cmp(PLL a, PLL b){
	if(a.x != b.x) return a.x > b.x;
	return a.y < b.y;
}

PLL intersect(PLL a, PLL b){
	LL A, B;
	A = a.y - b.y;
	B = b.x - a.x;
	if(B < 0) A = -A, B = -B;
	return {A, B};
}

vector<PLL> line;

void add(PLL nw){
	while(SZ(line)>1){
		int a = SZ(line);
		if(line[a-1].x == nw.x) return;
		PLL tmp1 = intersect(line[a-2], line[a-1]);
		PLL tmp2 = intersect(line[a-1], nw);
		if((__int128)tmp2.x*(__int128)tmp1.y <= (__int128)tmp1.x*(__int128)tmp2.y) line.pop_back();
		else break;
	}
	line.pb(nw);
}

LD calc(LD a, int b){
	return a*line[b].x + line[b].y;
}

LL L;
int n;

int main(){
	int i,j;
	LL a,b, dist0 = 2e18+2, distL = 2e18+2;
 	LD ans;
	scanf("%d %lld",&n,&L);
	for(i=1;i<=n;i++){
		scanf("%lld%lld",&a,&b);
		dist0 = min(dist0, a*a + b*b);
		distL = min(distL, (L-a)*(L-a) + b*b);
		tower[i] = {-a*2ll, a*a + b*b};
	}
	ans = (LD)max(dist0, distL);
    for(i=1;i<=n;i++) add(tower[i]);
    for(i = 0; i < SZ(line)-1; i++){
    	PLL tmp = intersect(line[i], line[i+1]);
    	LD tmp2 = (LD)tmp.x/tmp.y;
    	if(tmp2 < 0 || tmp2 > L) continue;
    	ans = max(ans, calc(tmp2, i) + tmp2*tmp2);
    }
    printf("%Lf",sqrt(ans));
    return 0;
}
/*
2 10
0 0
11 1

3 10
1 0
5 0
10 0

2 10
-5 3
12 2
*/

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:52:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
mobile.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&L);
  ~~~~~^~~~~~~~~~~~~~~~~
mobile.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Incorrect 3 ms 504 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1944 KB Output is correct
2 Correct 31 ms 1656 KB Output is correct
3 Correct 14 ms 1400 KB Output is correct
4 Correct 26 ms 1656 KB Output is correct
5 Incorrect 12 ms 1272 KB Output isn't correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4076 KB Output is correct
2 Correct 23 ms 1784 KB Output is correct
3 Correct 23 ms 3916 KB Output is correct
4 Correct 38 ms 2116 KB Output is correct
5 Incorrect 23 ms 1784 KB Output isn't correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2040 KB Output is correct
2 Correct 35 ms 2040 KB Output is correct
3 Correct 24 ms 2528 KB Output is correct
4 Correct 38 ms 2168 KB Output is correct
5 Correct 29 ms 2040 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3204 KB Output is correct
2 Correct 27 ms 2024 KB Output is correct
3 Correct 25 ms 2552 KB Output is correct
4 Correct 38 ms 2168 KB Output is correct
5 Correct 29 ms 2040 KB Output is correct

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16604 KB Output is correct
2 Correct 133 ms 8288 KB Output is correct
3 Correct 130 ms 8444 KB Output is correct
4 Correct 176 ms 8276 KB Output is correct
5 Incorrect 144 ms 8352 KB Output isn't correct

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 8312 KB Output is correct
2 Correct 131 ms 9524 KB Output is correct
3 Correct 111 ms 10464 KB Output is correct
4 Correct 175 ms 8432 KB Output is correct
5 Incorrect 146 ms 8240 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 26452 KB Output is correct
2 Correct 151 ms 9840 KB Output is correct
3 Correct 149 ms 9976 KB Output is correct
4 Correct 214 ms 10088 KB Output is correct
5 Incorrect 165 ms 9864 KB Output isn't correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 9780 KB Output is correct
2 Correct 158 ms 11124 KB Output is correct
3 Correct 130 ms 12168 KB Output is correct
4 Correct 212 ms 9976 KB Output is correct
5 Correct 176 ms 9852 KB Output is correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28060 KB Output is correct
2 Correct 178 ms 11464 KB Output is correct
3 Correct 172 ms 11576 KB Output is correct
4 Correct 247 ms 11512 KB Output is correct
5 Incorrect 185 ms 11608 KB Output isn't correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 11376 KB Output is correct
2 Correct 184 ms 12640 KB Output is correct
3 Correct 155 ms 13628 KB Output is correct
4 Correct 248 ms 11640 KB Output is correct
5 Incorrect 202 ms 11512 KB Output isn't correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 29520 KB Output is correct
2 Correct 257 ms 12964 KB Output is correct
3 Correct 195 ms 13300 KB Output is correct
4 Correct 286 ms 13176 KB Output is correct
5 Incorrect 226 ms 13176 KB Output isn't correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 12928 KB Output is correct
2 Correct 218 ms 14192 KB Output is correct
3 Correct 175 ms 15208 KB Output is correct
4 Correct 280 ms 13176 KB Output is correct
5 Incorrect 230 ms 13048 KB Output isn't correct

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 32728 KB Output is correct
2 Correct 249 ms 16120 KB Output is correct
3 Correct 261 ms 16208 KB Output is correct
4 Correct 352 ms 16164 KB Output is correct
5 Incorrect 274 ms 16348 KB Output isn't correct

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 16120 KB Output is correct
2 Correct 260 ms 18464 KB Output is correct
3 Correct 226 ms 20332 KB Output is correct
4 Correct 350 ms 15996 KB Output is correct
5 Incorrect 290 ms 16120 KB Output isn't correct