oj.uz

Submission #638861

# Submission time Handle Problem Language Result Execution time Memory
638861 2022-09-07T18:04:56 Z luanaamorim Mobile (BOI12_mobile) C++14
0 / 100
 1000 ms 40496 KB 
#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;
	}

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

Subtask #1
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 #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Incorrect 4 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 34020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 38356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 40496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 38864 KB Time limit exceeded
2 Halted 0 ms 0 KB -