oj.uz

Submission #972686

# Submission time Handle Problem Language Result Execution time Memory
972686 2024-04-30T21:45:52 Z iag99 Mobile (BOI12_mobile) C++17
100 / 100
 410 ms 16640 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

struct Point{
	double x,y;
};
double max_point(const Point &a, const Point &b)
{
	return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) /
	       (2 * b.x - 2 * a.x);
}
double dist(const Point &a, const Point &b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,l;
	cin>>n>>l;
	deque<Point> needed;
	for(int i=0; i<n; i++)
	{
		Point cur;
		cin>>cur.x>>cur.y;
		cur.y=abs(cur.y);
		if((int)needed.size() && needed.back().x==cur.x)
		{
			if(cur.y>=needed.back().y)
			{
				continue;
			}
			else
			{
				needed.pop_back();
			}
		}
		while((int)needed.size()>1 && max_point(needed[needed.size()-2], needed.back())>max_point(needed.back(),cur))
		{
			needed.pop_back();
		}
		needed.push_back(cur);
		
	}
	while ((int)needed.size() > 1 && max_point(needed[0], needed[1]) < 0) {
		needed.pop_front();
	}

	while ((int)needed.size() > 1 &&
	       max_point(needed[(int)needed.size() - 2], needed.back()) > l) {
		needed.pop_back();
	}
	double ans=0;
	for(int x=0; x<(int)needed.size(); x++)
	{
		Point left={0,0};
		Point right={l,0};
		if (x) { left.x = max_point(needed[x], needed[x - 1]); }
		if (x < (int)needed.size() - 1) {
			right.x = max_point(needed[x], needed[x + 1]);
		}

		if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) {
			continue;
		}
		if(left.x>=0 && left.x<=l) ans=max(ans, dist(needed[x], left));
		if(right.x>=0 && right.x<=l) ans=max(ans, dist(needed[x], right));
		//ans = max({ans, dist(needed[x], left), dist(needed[x], right)});
	}
		cout << fixed << setprecision(6) << ans << endl;

	
	return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:59:16: warning: narrowing conversion of 'l' from 'int' to 'double' [-Wnarrowing]
   59 |   Point right={l,0};
      |                ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 0 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 #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 344 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 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 456 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 348 KB Output is correct
2 Correct 26 ms 348 KB Output is correct
3 Correct 17 ms 348 KB Output is correct
4 Correct 28 ms 348 KB Output is correct
5 Correct 14 ms 456 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 348 KB Output is correct
2 Correct 24 ms 348 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 344 KB Output is correct
5 Correct 33 ms 344 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1884 KB Output is correct
2 Correct 28 ms 1116 KB Output is correct
3 Correct 28 ms 2396 KB Output is correct
4 Correct 40 ms 1628 KB Output is correct
5 Correct 32 ms 1204 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 448 KB Output is correct
2 Correct 33 ms 600 KB Output is correct
3 Correct 30 ms 604 KB Output is correct
4 Correct 40 ms 452 KB Output is correct
5 Correct 34 ms 348 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1200 KB Output is correct
2 Correct 33 ms 348 KB Output is correct
3 Correct 30 ms 628 KB Output is correct
4 Correct 43 ms 344 KB Output is correct
5 Correct 35 ms 344 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 8648 KB Output is correct
2 Correct 167 ms 4400 KB Output is correct
3 Correct 165 ms 4284 KB Output is correct
4 Correct 230 ms 5456 KB Output is correct
5 Correct 193 ms 3924 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 428 KB Output is correct
2 Correct 169 ms 1100 KB Output is correct
3 Correct 173 ms 1940 KB Output is correct
4 Correct 194 ms 452 KB Output is correct
5 Correct 190 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 10232 KB Output is correct
2 Correct 210 ms 5300 KB Output is correct
3 Correct 195 ms 4900 KB Output is correct
4 Correct 239 ms 6480 KB Output is correct
5 Correct 213 ms 4908 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 344 KB Output is correct
2 Correct 204 ms 1316 KB Output is correct
3 Correct 190 ms 1496 KB Output is correct
4 Correct 248 ms 348 KB Output is correct
5 Correct 213 ms 592 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 11748 KB Output is correct
2 Correct 238 ms 5972 KB Output is correct
3 Correct 243 ms 5992 KB Output is correct
4 Correct 279 ms 7336 KB Output is correct
5 Correct 240 ms 5312 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 348 KB Output is correct
2 Correct 239 ms 1376 KB Output is correct
3 Correct 225 ms 2588 KB Output is correct
4 Correct 279 ms 452 KB Output is correct
5 Correct 250 ms 452 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 13540 KB Output is correct
2 Correct 265 ms 6740 KB Output is correct
3 Correct 264 ms 6372 KB Output is correct
4 Correct 341 ms 8636 KB Output is correct
5 Correct 287 ms 6192 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 436 KB Output is correct
2 Correct 272 ms 1404 KB Output is correct
3 Correct 260 ms 2368 KB Output is correct
4 Correct 319 ms 452 KB Output is correct
5 Correct 301 ms 452 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 16640 KB Output is correct
2 Correct 334 ms 8372 KB Output is correct
3 Correct 331 ms 7672 KB Output is correct
4 Correct 410 ms 10324 KB Output is correct
5 Correct 363 ms 7336 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 436 KB Output is correct
2 Correct 339 ms 1364 KB Output is correct
3 Correct 312 ms 2872 KB Output is correct
4 Correct 397 ms 448 KB Output is correct
5 Correct 369 ms 448 KB Output is correct