답안 #972686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972686	2024-04-30T21:45:52 Z	iag99	Mobile (BOI12_mobile)	C++17	100 / 100	410 ms	16640 KB

mobile

#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

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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