oj.uz

Submission #56119

# Submission time Handle Problem Language Result Execution time Memory
56119 2018-07-10T04:45:17 Z gs14004 Mobile (BOI12_mobile) C++17
100 / 100
 486 ms 16848 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;

int n, l;
pi a[1000005];
deque<pi> stk;

double cross(pi a, pi b){
	int x1 = a.first, x2 = b.first, y1 = a.second, y2 = b.second;
	return 1.0 * (1ll * x2 * x2 + 1ll * y2 * y2 - 1ll * x1 * x1 - 1ll * y1 * y1) / (2.0 * (x2 - x1));
}

double solve(double s, double e, pi t){
	return max(hypot(s - t.first, t.second), hypot(e - t.first, t.second));
}

int main(){
	scanf("%d %d",&n,&l);
	for (int i=0; i<n; i++) {
		scanf("%d %d",&a[i].first, &a[i].second);
		a[i].second = abs(a[i].second);
	}
	sort(a, a+n);
	for (int i=0; i<n; ) {
		int e = i;
		while(e < n && a[e].first == a[i].first) e++;
		while (stk.size() >= 2 && cross(stk[stk.size()-2], stk.back()) > cross(stk.back(), a[i])) {
			stk.pop_back();
		}
		stk.push_back(a[i]);
		i = e;
	}
	double ret = 0;
	while(stk.size() >= 2 && cross(stk[0], stk[1]) < 0) stk.pop_front();
	while(stk.size() >= 2 && cross(stk[stk.size()-2], stk.back()) > l) stk.pop_back();
	ret = max(ret, solve(0, cross(stk[0], stk[1]), stk[0]));
	ret = max(ret, solve(cross(stk[stk.size()-2], stk.back()), l, stk.back()));
	for(int i=1; i+1<stk.size(); i++){
		ret = max(ret, solve(cross(stk[i-1], stk[i]), cross(stk[i], stk[i+1]), stk[i]));
	}
	printf("%lf",ret);
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i+1<stk.size(); i++){
               ~~~^~~~~~~~~~~
mobile.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
mobile.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1260 KB Output is correct
2 Correct 34 ms 1260 KB Output is correct
3 Correct 22 ms 1260 KB Output is correct
4 Correct 27 ms 1260 KB Output is correct
5 Correct 18 ms 1260 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1260 KB Output is correct
2 Correct 26 ms 1260 KB Output is correct
3 Correct 30 ms 1260 KB Output is correct
4 Correct 32 ms 1260 KB Output is correct
5 Correct 40 ms 1388 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2028 KB Output is correct
2 Correct 31 ms 2028 KB Output is correct
3 Correct 31 ms 2028 KB Output is correct
4 Correct 43 ms 2028 KB Output is correct
5 Correct 33 ms 2028 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2028 KB Output is correct
2 Correct 36 ms 2028 KB Output is correct
3 Correct 31 ms 2028 KB Output is correct
4 Correct 44 ms 2028 KB Output is correct
5 Correct 39 ms 2028 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2028 KB Output is correct
2 Correct 33 ms 2028 KB Output is correct
3 Correct 35 ms 2028 KB Output is correct
4 Correct 45 ms 2028 KB Output is correct
5 Correct 59 ms 2028 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 8572 KB Output is correct
2 Correct 182 ms 8572 KB Output is correct
3 Correct 164 ms 8572 KB Output is correct
4 Correct 193 ms 8572 KB Output is correct
5 Correct 166 ms 8572 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 8572 KB Output is correct
2 Correct 204 ms 8572 KB Output is correct
3 Correct 152 ms 8572 KB Output is correct
4 Correct 304 ms 8572 KB Output is correct
5 Correct 171 ms 8572 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 10232 KB Output is correct
2 Correct 193 ms 10232 KB Output is correct
3 Correct 173 ms 10232 KB Output is correct
4 Correct 233 ms 10232 KB Output is correct
5 Correct 197 ms 10232 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10232 KB Output is correct
2 Correct 194 ms 10232 KB Output is correct
3 Correct 284 ms 10232 KB Output is correct
4 Correct 240 ms 10232 KB Output is correct
5 Correct 256 ms 10232 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 11904 KB Output is correct
2 Correct 269 ms 11904 KB Output is correct
3 Correct 224 ms 11904 KB Output is correct
4 Correct 283 ms 11904 KB Output is correct
5 Correct 204 ms 11904 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 11904 KB Output is correct
2 Correct 269 ms 11904 KB Output is correct
3 Correct 289 ms 11904 KB Output is correct
4 Correct 392 ms 11904 KB Output is correct
5 Correct 256 ms 11904 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 13568 KB Output is correct
2 Correct 251 ms 13568 KB Output is correct
3 Correct 221 ms 13568 KB Output is correct
4 Correct 365 ms 13568 KB Output is correct
5 Correct 310 ms 13568 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 13568 KB Output is correct
2 Correct 277 ms 13568 KB Output is correct
3 Correct 320 ms 13568 KB Output is correct
4 Correct 297 ms 13568 KB Output is correct
5 Correct 264 ms 13568 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 16848 KB Output is correct
2 Correct 280 ms 16848 KB Output is correct
3 Correct 297 ms 16848 KB Output is correct
4 Correct 446 ms 16848 KB Output is correct
5 Correct 486 ms 16848 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 16848 KB Output is correct
2 Correct 354 ms 16848 KB Output is correct
3 Correct 274 ms 16848 KB Output is correct
4 Correct 438 ms 16848 KB Output is correct
5 Correct 391 ms 16848 KB Output is correct