Submission #638862

#	Time	Username	Problem	Language	Result	Execution time	Memory
638862		luanaamorim	Mobile (BOI12_mobile)	C++14	0 / 100	1088 ms	31936 KiB

mobile

#include <bits/stdc++.h>
#define MAX (int)(1e6 + 5)
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define bug(x) cout << #x << " - " << x << endl

using namespace std;

double n, l, a[MAX], b[MAX];
vector<pair<double, double> > resp;
pair<double, double> last, now;

double dist(pair<double, double> a, pair<double, double> b)
{
	return (a.first-b.first)*(a.first-b.first) + (b.second-a.second)*(b.second-a.second);
}

int pode(pair<double, double> last, pair<double, double> now, double pos)
{
	return (dist(last, {pos, 0}) <= dist(now, {pos, 0}));
}

double bb(pair<double, double> last, pair<double, double> now)
{
	int k = 40;
	double mid, ini = last.first, fim = now.first;
	while (k--)
	{
		mid = (ini+fim)/2;
		if (pode(last, now, mid)) ini = mid;
		else fim = mid;
	}

	return mid;
}

int main()
{
	cin >> n >> l;
	cin >> a[0] >> b[0];
	if (n == 1)
	{
		if (dist({0, 0}, {a[0], b[0]}) > dist({l, l}, {a[0], b[0]})) cout << 0 << endl;
		else cout << l << endl;
		return 0;
	}
	last = {a[0], b[0]};
	for (int i = 1; i < n; i++)
	{
		cin >> a[i] >> b[i];
		now = {a[i], b[i]};
		double tmp = bb(last, now);
		resp.push_back({min(dist(last, {tmp, 0}), dist(now, {tmp, 0})), tmp});
		// if (dist(last, {tmp, 0}) > dist(now, {tmp, 0})) last = now;
		last = now;
	}

	sort(resp.begin(), resp.end(), greater<pair<double, double> >());
	cout << fixed << setprecision(6) << resp[0].second << endl;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 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