oj.uz

Submission #554949

# Submission time Handle Problem Language Result Execution time Memory
554949 2022-04-29T17:44:16 Z victor_gao Mobile (BOI12_mobile) C++17
0 / 100
 894 ms 31556 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define double long double
#define pii pair<int,int>
#define x first
#define y second
#define N 1000015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,L;
pii arr[N];
bool check(double val){
	//cout<<sqrt(val)<<" -> \n";
	double l=0,r=-1;
	for (int i=1;i<=n;i++){
		if (val*val-arr[i].y*arr[i].y<=0.000001) continue;
		double dl=(double)arr[i].x-sqrt(val*val-arr[i].y*arr[i].y);
		double dr=(double)arr[i].x+sqrt(val*val-arr[i].y*arr[i].y);
		if (l<r){
			if (dl-r>0.000001){
				l=dl;
			}
			else {
				r=max(r,dr);
				l=min(l,dl);
			}
		}
		else {
			if (r-dl>0.000001){
				r=dr;
				l=dl;
			}
		}
//		cout<<l<<" "<<r<<'\n';
	}
	if (l<=r&&r>=L){
	//	cout<<"OK\n";
		return 1;
	}
//	cout<<"NO\n";
	return 0;
}
bool cmp(pii a,pii b){
	if (a.x!=b.x) return a.x<b.x;
	else return a.y>b.y;
} 
signed main(){
	fast
//	freopen("loan.in","r",stdin);
//	freopen("loan.out","w",stdout);
	cout<<fixed<<setprecision(5);
	cin>>n>>L;
	for (int i=1;i<=n;i++) cin>>arr[i].x>>arr[i].y;
	sort(arr+1,arr+1+n,cmp);
	double l=0,r=4e18;
	while (r-l>0.00001){
		double mid=(l+r)/2.0;
	//	cout<<l<<" ~ "<<r<<'\n';
		if (check(mid)) r=mid;
		else l=mid;
	}
	cout<<(double)(l)<<'\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Incorrect 5 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 408 KB Output is correct
2 Incorrect 5 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 1496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 1496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1696 KB Output is correct
2 Incorrect 69 ms 1612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1880 KB Output is correct
2 Incorrect 89 ms 1888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 8144 KB Output is correct
2 Incorrect 421 ms 15920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 8104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 9712 KB Output is correct
2 Incorrect 539 ms 19000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 535 ms 9712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 11280 KB Output is correct
2 Incorrect 672 ms 22140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 592 ms 11272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 12844 KB Output is correct
2 Incorrect 721 ms 25292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 699 ms 12876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 15964 KB Output is correct
2 Incorrect 894 ms 31556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 881 ms 15960 KB Output isn't correct
2 Halted 0 ms 0 KB -