Submission #544782

#	Time	Username	Problem	Language	Result	Execution time	Memory
544782		rainboy	Balloons (CEOI11_bal)	C++98	100 / 100	132 ms	9832 KiB

bal

#include <math.h>
#include <stdio.h>

#define N	200000

double min(double a, double b) { return a < b ? a : b; }

int xx[N]; double yy[N], yy_[N];

double f(int i, int j) {
	return (xx[j] * yy_[i] - xx[i] * yy_[j]) / (yy_[i] - yy_[j]);
}

int main() {
	static int qu[N];
	int n, i, cnt;

	scanf("%d", &n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		int r, i_;

		scanf("%d%d", &xx[i], &r);
		while (cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= xx[i])
			cnt--;
		i_ = cnt == 0 ? -1 : qu[cnt - 1];
		yy[i] = cnt == 0 ? r : min(r, (double) (xx[i] - xx[i_]) * (xx[i] - xx[i_]) / 4 / yy[i_]);
		yy_[i] = sqrt(yy[i]);
		printf("%f\n", yy[i]);
		while (cnt && (yy[qu[cnt - 1]] <= yy[i] || cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= f(qu[cnt - 1], i)))
			cnt--;
		qu[cnt++] = i;
	}
	return 0;
}

Compilation message (stderr)

bal.cpp: In function 'int main()':
bal.cpp:30:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |   while (cnt && (yy[qu[cnt - 1]] <= yy[i] || cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) <= f(qu[cnt - 1], i)))
      |                                              ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bal.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bal.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d%d", &xx[i], &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10