oj.uz

Submission #489650

# Submission time Handle Problem Language Result Execution time Memory
489650 2021-11-23T14:07:16 Z rainboy Svjetlost (COI18_svjetlost) C++17
40 / 100
 3000 ms 3032 KB 
#include <math.h>
#include <stdio.h>

#define N	100000

double max(double a, double b) { return a > b ? a : b; }

int xx[N], yy[N], n; char dead[N];

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

long long dot(int x1, int y1, int x2, int y2) {
	return (long long) x1 * x2 + (long long) y1 * y2;
}

int check(int x1, int y1, int x2, int y2) {
	long long c = cross(x1, y1, x2, y2);

	return c != 0 ? c > 0 : dot(x1, y1, x2, y2) > 0;
}

double solve() {
	static int ii[N];
	int h, h_, i, cnt;
	double d, d_;

	cnt = 0;
	for (i = 0; i < n; i++)
		if (!dead[i])
			ii[cnt++] = i;
	d = 0, d_ = 0;
	for (h = 0, h_ = 0; h < cnt; h++) {
		while (check(xx[ii[(h + 1) % cnt]] - xx[ii[h]], yy[ii[(h + 1) % cnt]] - yy[ii[h]], xx[ii[(h_ + 1) % cnt]] - xx[ii[h_]], yy[ii[(h_ + 1) % cnt]] - yy[ii[h_]])) {
			d += hypot(xx[ii[(h_ + 1) % cnt]] - xx[ii[h_]], yy[ii[(h_ + 1) % cnt]] - yy[ii[h_]]);
			h_ = (h_ + 1) % cnt;
		}
		d_ = max(d_, d);
		d -= hypot(xx[ii[(h + 1) % cnt]] - xx[ii[h]], yy[ii[(h + 1) % cnt]] - yy[ii[h]]);
	}
	return d_;
}

int main() {
	int q, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	scanf("%d", &q);
	printf("%f\n", solve());
	while (q--) {
		int i;

		scanf("%d", &i), i--;
		dead[i] = 1;
		printf("%f\n", solve());
	}
	return 0;
}

Compilation message

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d", &i), i--;
      |   ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB 11 numbers
2 Correct 0 ms 208 KB 41 numbers
3 Correct 1 ms 208 KB 11 numbers
4 Correct 1 ms 208 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB 11 numbers
2 Correct 0 ms 208 KB 41 numbers
3 Correct 1 ms 208 KB 11 numbers
4 Correct 1 ms 208 KB 93 numbers
5 Correct 5 ms 208 KB 101 numbers
6 Correct 47 ms 304 KB 1201 numbers
7 Correct 70 ms 364 KB 1556 numbers
8 Correct 106 ms 376 KB 1996 numbers
9 Correct 87 ms 360 KB 1960 numbers
10 Correct 99 ms 500 KB 1991 numbers
11 Correct 93 ms 336 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 1 ms 336 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 3 ms 556 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 7 ms 832 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 25 ms 3032 KB found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 26 ms 3016 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 376 KB 1001 numbers
2 Execution timed out 3080 ms 1308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB 11 numbers
2 Correct 0 ms 208 KB 41 numbers
3 Correct 1 ms 208 KB 11 numbers
4 Correct 1 ms 208 KB 93 numbers
5 Correct 5 ms 208 KB 101 numbers
6 Correct 47 ms 304 KB 1201 numbers
7 Correct 70 ms 364 KB 1556 numbers
8 Correct 106 ms 376 KB 1996 numbers
9 Correct 87 ms 360 KB 1960 numbers
10 Correct 99 ms 500 KB 1991 numbers
11 Correct 93 ms 336 KB 1963 numbers
12 Correct 0 ms 208 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 1 ms 336 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 3 ms 556 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 7 ms 832 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 25 ms 3032 KB found '3142086769.6889629364', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 26 ms 3016 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 102 ms 376 KB 1001 numbers
19 Execution timed out 3080 ms 1308 KB Time limit exceeded
20 Halted 0 ms 0 KB -