Submission #489650

#	Time	Username	Problem	Language	Result	Execution time	Memory
489650		rainboy	Svjetlost (COI18_svjetlost)	C++17	40 / 100	3080 ms	3032 KiB

Main

#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 (stderr)

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 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31