oj.uz

Submission #133173

# Submission time Handle Problem Language Result Execution time Memory
133173 2019-07-20T08:33:36 Z sealnot123 Mobile (BOI12_mobile) C++14
100 / 100
 436 ms 32484 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1000007;
PLL tower[N];

bool cmp(PLL a, PLL b){
	if(a.x != b.x) return a.x > b.x;
	return a.y < b.y;
}

PLL intersect(PLL a, PLL b){
	LL A, B;
	A = a.y - b.y;
	B = b.x - a.x;
	if(B < 0) A = -A, B = -B;
	return {A, B};
}

vector<PLL> line;

void add(PLL nw){
	while(SZ(line)>1){
		int a = SZ(line);
		if(line[a-1].x == nw.x) return;
		PLL tmp1 = intersect(line[a-2], line[a-1]);
		PLL tmp2 = intersect(line[a-1], nw);
		if((__int128)tmp2.x*(__int128)tmp1.y <= (__int128)tmp1.x*(__int128)tmp2.y) line.pop_back();
		else break;
	}
	line.pb(nw);
}

LD calc(LD a, int b){
	return a*line[b].x + line[b].y;
}

LL L;
int n;

int main(){
	int i,j;
	LL a,b, dist0 = 2e18+2, distL = 2e18+2;
 	LD ans;
	scanf("%d %lld",&n,&L);
	for(i=1;i<=n;i++){
		scanf("%lld%lld",&a,&b);
		dist0 = min(dist0, a*a + b*b);
		distL = min(distL, (L-a)*(L-a) + b*b);
		tower[i] = {-a*2ll, a*a + b*b};
	}
	ans = (LD)max(dist0, distL);
	sort(tower+1, tower+1+n, cmp);
    for(i=1;i<=n;i++) add(tower[i]);
    for(i = 0; i < SZ(line)-1; i++){
    	PLL tmp = intersect(line[i], line[i+1]);
    	LD tmp2 = (LD)tmp.x/tmp.y;
    	if(tmp2 < 0 || tmp2 > L) continue;
    	ans = max(ans, calc(tmp2, i) + tmp2*tmp2);
    }
    printf("%Lf",sqrt(ans));
    return 0;
}
/*
2 10
0 0
11 1

3 10
1 0
5 0
10 0

2 10
-5 3
12 2
*/

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:52:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
mobile.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&L);
  ~~~~~^~~~~~~~~~~~~~~~~
mobile.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 412 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1784 KB Output is correct
2 Correct 28 ms 1528 KB Output is correct
3 Correct 18 ms 1272 KB Output is correct
4 Correct 30 ms 1532 KB Output is correct
5 Correct 15 ms 1144 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1528 KB Output is correct
2 Correct 25 ms 1528 KB Output is correct
3 Correct 30 ms 1784 KB Output is correct
4 Correct 32 ms 1784 KB Output is correct
5 Correct 36 ms 1784 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3820 KB Output is correct
2 Correct 29 ms 1656 KB Output is correct
3 Correct 29 ms 3820 KB Output is correct
4 Correct 44 ms 1952 KB Output is correct
5 Correct 29 ms 2684 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1912 KB Output is correct
2 Correct 35 ms 1912 KB Output is correct
3 Correct 32 ms 2424 KB Output is correct
4 Correct 44 ms 2040 KB Output is correct
5 Correct 36 ms 3188 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3060 KB Output is correct
2 Correct 35 ms 1912 KB Output is correct
3 Correct 30 ms 2452 KB Output is correct
4 Correct 45 ms 1944 KB Output is correct
5 Correct 37 ms 3168 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16520 KB Output is correct
2 Correct 172 ms 8144 KB Output is correct
3 Correct 170 ms 8384 KB Output is correct
4 Correct 214 ms 8232 KB Output is correct
5 Correct 183 ms 14944 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 8188 KB Output is correct
2 Correct 172 ms 9564 KB Output is correct
3 Correct 152 ms 10488 KB Output is correct
4 Correct 212 ms 8312 KB Output is correct
5 Correct 191 ms 15392 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 26380 KB Output is correct
2 Correct 206 ms 9720 KB Output is correct
3 Correct 205 ms 9848 KB Output is correct
4 Correct 261 ms 9904 KB Output is correct
5 Correct 220 ms 17816 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 9720 KB Output is correct
2 Correct 207 ms 10960 KB Output is correct
3 Correct 179 ms 11976 KB Output is correct
4 Correct 265 ms 9868 KB Output is correct
5 Correct 223 ms 18516 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 27968 KB Output is correct
2 Correct 257 ms 11228 KB Output is correct
3 Correct 239 ms 11380 KB Output is correct
4 Correct 311 ms 11588 KB Output is correct
5 Correct 247 ms 20452 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 11256 KB Output is correct
2 Correct 242 ms 12656 KB Output is correct
3 Correct 215 ms 13544 KB Output is correct
4 Correct 302 ms 11512 KB Output is correct
5 Correct 262 ms 21496 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 29452 KB Output is correct
2 Correct 280 ms 12808 KB Output is correct
3 Correct 279 ms 13260 KB Output is correct
4 Correct 360 ms 13048 KB Output is correct
5 Correct 304 ms 24088 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 12940 KB Output is correct
2 Correct 274 ms 13936 KB Output is correct
3 Correct 253 ms 15276 KB Output is correct
4 Correct 348 ms 13020 KB Output is correct
5 Correct 298 ms 24648 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 32484 KB Output is correct
2 Correct 352 ms 16120 KB Output is correct
3 Correct 342 ms 16128 KB Output is correct
4 Correct 429 ms 16052 KB Output is correct
5 Correct 360 ms 29688 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 16120 KB Output is correct
2 Correct 342 ms 18152 KB Output is correct
3 Correct 313 ms 20300 KB Output is correct
4 Correct 436 ms 15992 KB Output is correct
5 Correct 379 ms 30852 KB Output is correct