Submission #398270

#	Time	Username	Problem	Language	Result	Execution time	Memory
398270		AriaH	Mobile (BOI12_mobile)	C++11	50 / 100	1092 ms	48064 KiB

mobile

/** vaziat sorati ghermeze **/

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const ld one = 1.;
const ld eps = 1e-15;

int n, L, X[N], Y[N];

ld base[N];

pair < ld, ld > arr[N];

int check(ld x)
{
	int ptr = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(abs(Y[i]) - x > eps) continue;
		ld l = sqrt(x * x - base[i]);
		arr[ptr ++] = Mp(X[i] - l, X[i] + l);
	}
	sort(arr, arr + ptr);
	ld right = 0;
	for(int i = 0; i < ptr; i ++)
	{
		if(arr[i].F - right > eps)
		{
			return 0;
		}
		if(arr[i].S - right > eps)
		{
			right = arr[i].S;
		}
		if(right - L > eps)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	scanf("%d%d", &n, &L);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d", &X[i], &Y[i]);
		base[i] = one * Y[i] * Y[i];
	}
	ld d = 0, up = 3e9;
	///printf("checking %d\n", check(6));
	for(int _ = 0; _ < 44; _ ++)
	{
		ld mid = (up + d) / 2.0;
		if(check(mid))
		{
			up = mid;
		}
		else
		{
			d = mid;
		}
	}
	printf("%.4lf", up);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d%d", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
mobile.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d%d", &X[i], &Y[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: 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