Submission #972684

#	Time	Username	Problem	Language	Result	Execution time	Memory
972684		iag99	Mobile (BOI12_mobile)	C++17	100 / 100	419 ms	25520 KiB

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;
		}

		ans = max({ans, dist(needed[x], left), dist(needed[x], right)});
	}
		cout << fixed << setprecision(6) << ans << endl;

	
	return 0;
}

Compilation message (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5