Submission #1073888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073888		vjudge1	Mobile (BOI12_mobile)	C++17	70 / 100	1057 ms	57868 KiB

mobile

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	ld L;
	cin >> n >> L;
	vector <pair<ld,ld>> pts;
	for(int i=0; i<n; i++){
		ld x, y;
		cin >> x >> y;
		if(!pts.empty() && x == pts.back().first){
			pts.back().second = min(pts.back().second, abs(y));
		}
		else{
			pts.push_back({x, abs(y)});
		}
	}
	n = pts.size();

	const ld EPS = 1e-4;
	ld l=0, r=3e9, mid;
	while(r-l>EPS){
		mid = (l+r)/2;

		vector <pair<ld,ld>> seg;

		for(int i=0; i<n; i++){
			ld x = pts[i].first, y = pts[i].second;
			if(mid <= y){
				continue;
			}
			ld d = sqrt(mid*mid-y*y);
			if(x-d <= L && x+d >= 0)
				seg.push_back({max((ld)0.0, x-d),min((ld)L, x+d)});
		}

		bool can = !seg.empty();
		if(can){
			sort(seg.begin(), seg.end());
			auto [st, en] = seg[0];
			for(int i=1; i<seg.size(); i++){
				auto [st2, en2] = seg[i];
				if(st2 > en){
					can = false;
					break;
				}
				en = max(en, en2);
			}
			if(abs(st)>EPS || abs(en-L) > EPS) can = false;
		}

		if(can) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(6) << l << '\n';
	return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=1; i<seg.size(); i++){
      |                 ~^~~~~~~~~~~

• 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: 0 / 5
• Subtask 13: 5 / 5
• Subtask 14: 0 / 5
• Subtask 15: 5 / 5
• Subtask 16: 0 / 5
• Subtask 17: 5 / 5
• Subtask 18: 0 / 5
• Subtask 19: 5 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5