Submission #459565

#	Time	Username	Problem	Language	Result	Execution time	Memory
459565		BackNoob	Mobile (BOI12_mobile)	C++14	13 / 100	1090 ms	10148 KiB

mobile

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define task "name"
#define ld long double
#define ull unsigned long long
using namespace std;
const ll mxN = 220797 + 7;
const ll inf = 1e9 + 277;
const ll mod = 2147483648;
const ll infll = 1e18 + 7;
const ll base = 307;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct Point{
	int x , y;
} a[mxN];

int n , L;

bool ok(ld x)
{
	vector<pair<ld , ld>> seg;
	for(int i = 1 ; i <= n ; i++) {
		ld h = abs(a[i].y);
		if(h > x) continue;
		if(h == x) seg.push_back({a[i].x , a[i].x});
		if(h < x) {
			ld leng = sqrt(x * x - h * h);
			ld l = a[i].x - leng;
			ld r = a[i].x + leng;
			seg.push_back({l , r});
		}
	}
	sort(seg.begin() , seg.end());

	ld minl = 0;
	for(auto it : seg) {
		ld l = it.fi;
		ld r = it.se;

		if(l > minl) return false;
		else minl = max(minl , r);
		if(minl >= L) return true;
	}
	return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   //	freopen("task.inp" , "r" , stdin);
   // freopen("task.out" , "w" , stdout);

   	cin >> n >> L;

   	for(int i = 1 ; i <= n ; i++) cin >> a[i].x >> a[i].y;

   	ld l = 0 , r = 1e18;
   	for(int i = 1 ; i <= 100 ; i++) {
   		ld mid = (l + r) / 2;

   		if(ok(mid)) r = mid;
   		else l = mid; 
   	}

   	cout << fixed << setprecision(6) << l;
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5