Submission #1280659

#TimeUsernameProblemLanguageResultExecution timeMemory
1280659goldenbullMobile (BOI12_mobile)C++17
36 / 100
1099 ms65324 KiB
#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FOD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define FUL(n) (((1LL)<<(n))-1)
#define BIT(n,k) (((n)>>(k))&1)
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define sqr(x) (1LL * (x) * (x))
using namespace std;
using ll = long long;
using ull = uint64_t;
using ld = long double;
template<class T> using ve = vector<T>;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;

const char el = '\n';
template<class T> void print(T a[], int n) { FOR(i,0,n-1) cerr << a[i] << ' '; cerr << el; }
template<class T, class U> bool maxi(T& x, const U& y) { return y>x?(x=y,1):0; }
template<class T, class U> bool mini(T& x, const U& y) { return y<x?(x=y,1):0; }

const int maxn = 1e6+7;
const ld eps = 1e-3;

int n;
ll L;
pll pt[maxn];

pld cover(ll x, ll y, ld r) {
	ld s = sqrt(abs(r*r - 1.0*y*y));
	return {1.0*x - s, 1.0*x + s};
}

bool ok(ld x) {
	ve<pld> lr;
	FOR(i,1,n) if (abs(pt[i].se) <= x) lr.pb(cover(pt[i].fi, pt[i].se, x));
	if (lr.empty()) return false;
	sort(all(lr));
	ld mx = 0;
	for (auto i:lr) {
		if (i.fi > mx) return false;
		maxi(mx, i.se);
	}
	return mx >= L;
}

// O(n log n log l), shouldn't pass
void solve() {
	cin>>n>>L;
	FOR(i,1,n) cin>>pt[i].fi>>pt[i].se;

	ld l = 0, r = 1e9+7;
	while (abs(l-r) > eps) {
		ld mid = (l+r)/2;
		if (ok(mid)) r = mid;
		else l = mid;
	}
	cout << fixed << setprecision(6);
	cout << l;
}

#define IN ".inp"
#define OUT ".out"
//#define NAME "test"
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	#ifndef NAME
		if (fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
	#endif
	#ifdef NAME
		freopen(NAME IN, "r", stdin);
		freopen(NAME OUT, "w", stdout);
	#endif

	int tt=1;
//	cin>>tt;
	while (tt--) solve();

	cerr << el << "Time elapsed: " << TIME << " s";
	return 0;
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:75:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |                 if (fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...