제출 #696439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696439		speedyArda	Mobile (BOI12_mobile)	C++14	90 / 100	1077 ms	82732 KiB

mobile

#include "bits/stdc++.h"

using namespace std;

const long long precision = 1e4; // TO not to deal with double/float precision problems // UPD: Didn't use it instaed used long double 
const int MAXN = 1e6+5;

//long long stations[MAXN][2];
vector < vector<long double> > stations;
int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long double  n, length;
	cin >> n >> length;
	//length *= precision;

	for(int i = 1; i <= n; i++)
	{
		long double x, y;
		cin >> x >> y;
		//x *= precision;
		//y *= precision;
		if(stations.size() == 0 || (stations.back())[0] != x)
			stations.push_back({x, y});
		else 
		{
			vector<long double> elem = stations.back();
			if(abs(elem[1]) > abs(y))
			{
				stations.pop_back();
				stations.push_back({x, y});
			}
		}
		/*cin >> stations[i][0] >> stations[i][1];
		stations[i][0]	*= precision;
		stations[i][1] *= precision;*/
	}



	long double l = 0, r = 3e9, ans = 3e9; // Max distance will be 3e9 as we can we have 2e9 vertical and 2e9 horizontal distance so according to the pythagoran sqrt(2e9^2 + 2e9^2)  =  2e9 * sqrt(2)

	while(r - l >= 0.0001)
	{
		long double m = (l + r) / 2.0000;
		long double left = length, right = 0;
		for(int i = 0; i < stations.size(); i++)
		{	
			long double x = stations[i][0], y = stations[i][1];
			//cout << x << " " << y << "\n";
			if(abs(y) > m)
				continue;
			
			long double horizontal = sqrt((m * m) - (y * y));
			//cout << x << " " << y << " " << m << " " << horizontal << "\n";
			if(x <= 0)
			{	
				

				if(x + horizontal >= 0)
				{
					left = 0, right = max(right, (long double) (x + horizontal)); 
				}

			} else 
			{
				long double templeft = max((long double)0.0000, (long double)(x - horizontal));
				long double tempright = min(length, (long double)(x + horizontal));
				if(templeft <= right)
				{
					left = min(left, max((long double)0.0000, templeft));
					right = max(right, min(length, tempright));
				}
			}
		}

		if(left <= 0 && right >= length)
		{
			ans = m;
			r = m - 0.0001;
		} else
			l = m + 0.0001;
	}


	cout << fixed << setprecision(10) << ans << "\n";



}

컴파일 시 표준 에러 (stderr) 메시지

mobile.cpp: In function 'int main()':
mobile.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i = 0; i < stations.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: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5