oj.uz

Submission #56138

# Submission time Handle Problem Language Result Execution time Memory
56138 2018-07-10T05:40:49 Z 김현수(#2106) Mobile (BOI12_mobile) C++11
100 / 100
 450 ms 32724 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 1000005, inf = 1e18;

ll n, l;
double head = inf, tail = inf;

pll a[N];
vector<pll> h;

double p (pll &A, pll &B) {
	return ((A.Y*A.Y - B.Y*B.Y) / (double) (A.X - B.X) + A.X + B.X) / 2.0;
}

int main()
{
	scanf("%lld%lld",&n,&l);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
		if(a[i].Y < 0) a[i].Y *= -1;
	}
	ll MN = inf;
	for(ll i=1;i<=n;i++) {
		MN = min(MN, a[i].Y);
		head = min(head, hypot(a[i].X, a[i].Y));
		tail = min(tail, hypot(a[i].X - l, a[i].Y));
		if(i < n && a[i+1].X == a[i].X) continue;
		pll T = {a[i].X, MN};
		MN = inf;
		while(h.size() > 1) {
			if(p(h[h.size()-2], h.back()) < p(h.back(), T)) break;
			else h.pop_back();
		}
		h.push_back(T);
	}
	double ans = max(head, tail);
	for(ll i=1;i<(int)h.size();i++) {
		double P = p(h[i-1], h[i]);
		if(0 > P || P > l) continue;
		ans = max(ans, hypot(h[i].X - P, h[i].Y));
	}
	printf("%.12f", ans);
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~~~~
mobile.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 5 ms 392 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 492 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 572 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 616 KB Output is correct
2 Correct 5 ms 744 KB Output is correct
3 Correct 5 ms 744 KB Output is correct
4 Correct 3 ms 744 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 744 KB Output is correct
2 Correct 6 ms 744 KB Output is correct
3 Correct 6 ms 744 KB Output is correct
4 Correct 5 ms 744 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 744 KB Output is correct
2 Correct 5 ms 744 KB Output is correct
3 Correct 5 ms 744 KB Output is correct
4 Correct 5 ms 744 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 748 KB Output is correct
2 Correct 6 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2028 KB Output is correct
2 Correct 40 ms 2028 KB Output is correct
3 Correct 35 ms 2028 KB Output is correct
4 Correct 48 ms 2028 KB Output is correct
5 Correct 26 ms 2028 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2028 KB Output is correct
2 Correct 43 ms 2028 KB Output is correct
3 Correct 42 ms 2028 KB Output is correct
4 Correct 35 ms 2028 KB Output is correct
5 Correct 50 ms 2028 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4060 KB Output is correct
2 Correct 50 ms 4060 KB Output is correct
3 Correct 55 ms 4064 KB Output is correct
4 Correct 58 ms 4064 KB Output is correct
5 Correct 38 ms 4064 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4064 KB Output is correct
2 Correct 60 ms 4064 KB Output is correct
3 Correct 51 ms 4064 KB Output is correct
4 Correct 70 ms 4064 KB Output is correct
5 Correct 49 ms 4064 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4064 KB Output is correct
2 Correct 48 ms 4064 KB Output is correct
3 Correct 35 ms 4064 KB Output is correct
4 Correct 68 ms 4064 KB Output is correct
5 Correct 65 ms 4064 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 16792 KB Output is correct
2 Correct 206 ms 16792 KB Output is correct
3 Correct 259 ms 16792 KB Output is correct
4 Correct 331 ms 16792 KB Output is correct
5 Correct 281 ms 16792 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 16792 KB Output is correct
2 Correct 262 ms 16792 KB Output is correct
3 Correct 238 ms 16792 KB Output is correct
4 Correct 190 ms 16792 KB Output is correct
5 Correct 166 ms 16792 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 26564 KB Output is correct
2 Correct 198 ms 26564 KB Output is correct
3 Correct 173 ms 26564 KB Output is correct
4 Correct 261 ms 26564 KB Output is correct
5 Correct 189 ms 26564 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 26564 KB Output is correct
2 Correct 192 ms 26564 KB Output is correct
3 Correct 182 ms 26564 KB Output is correct
4 Correct 234 ms 26564 KB Output is correct
5 Correct 211 ms 26564 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 28096 KB Output is correct
2 Correct 233 ms 28096 KB Output is correct
3 Correct 192 ms 28096 KB Output is correct
4 Correct 277 ms 28096 KB Output is correct
5 Correct 243 ms 28096 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 28096 KB Output is correct
2 Correct 220 ms 28096 KB Output is correct
3 Correct 226 ms 28096 KB Output is correct
4 Correct 303 ms 28096 KB Output is correct
5 Correct 237 ms 28096 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 29604 KB Output is correct
2 Correct 226 ms 29604 KB Output is correct
3 Correct 355 ms 29604 KB Output is correct
4 Correct 440 ms 29604 KB Output is correct
5 Correct 419 ms 29604 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 29604 KB Output is correct
2 Correct 389 ms 29604 KB Output is correct
3 Correct 339 ms 29604 KB Output is correct
4 Correct 450 ms 29604 KB Output is correct
5 Correct 276 ms 29604 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 32724 KB Output is correct
2 Correct 305 ms 32724 KB Output is correct
3 Correct 303 ms 32724 KB Output is correct
4 Correct 389 ms 32724 KB Output is correct
5 Correct 315 ms 32724 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 32724 KB Output is correct
2 Correct 292 ms 32724 KB Output is correct
3 Correct 246 ms 32724 KB Output is correct
4 Correct 395 ms 32724 KB Output is correct
5 Correct 337 ms 32724 KB Output is correct