Submission #721400

#	Time	Username	Problem	Language	Result	Execution time	Memory
721400		rainboy	2circles (balkan11_2circles)	C++17	80 / 100	656 ms	4800 KiB

twocircles

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

#define N	50000

typedef long double ld;

ld cross2(ld x1, ld y1, ld x2, ld y2) {
	return x1 * y2 - x2 * y1;
}

ld cross(ld x0, ld y0, ld x1, ld y1, ld x2, ld y2) {
	return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

ld dot2(ld x1, ld y1, ld x2, ld y2) {
	return x1 * x2 + y1 * y2;
}

int xx[N], yy[N], n;
ld aa[N], bb[N], cc[N];

void intersect(int i, int j, ld *x, ld *y) {
	ld u = cross2(cc[i], bb[i], cc[j], bb[j]);
	ld v = cross2(aa[i], cc[i], aa[j], cc[j]);
	ld w = cross2(aa[i], bb[i], aa[j], bb[j]);

	*x = u / w, *y = v / w;
}

int check_(int i, int j) {
	if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
		return check_(j, i);
	if (aa[i] != 0)
		return cross2(aa[i], cc[i], aa[j], cc[j]) < 0;
	else
		return cross2(bb[i], cc[i], bb[j], cc[j]) < 0;
}

int check(int i, int j, int k) {
	ld x1, y1, x2, y2;

	if (cross2(aa[i], bb[i], aa[j], bb[j]) == 0 && !check_(i, j))
		return 0;
	if (cross2(aa[j], bb[j], aa[k], bb[k]) == 0 && !check_(j, k))
		return 0;
	if (cross2(aa[i], bb[i], aa[j], bb[j]) <= 0 || cross2(aa[j], bb[j], aa[k], bb[k]) <= 0)
		return 1;
	intersect(i, j, &x1, &y1), intersect(j, k, &x2, &y2);
	return cross2(aa[j], bb[j], x2 - x1, y2 - y1) < 0;
}

int bad(int i, int j, int k) {
	return !check(i, j, k) && !check(j, k, i) && !check(k, i, j);
}

int solve(ld r) {
	static int qu[N];
	static ld xx_[N], yy_[N];
	int h, h_, i, j, head, cnt;

	for (i = 0; i < n; i++) {
		j = (i + 1) % n;
		aa[i] = yy[i] - yy[j];
		bb[i] = xx[j] - xx[i];
		cc[i] = dot2(aa[i], bb[i], xx[i], yy[i]) + hypotl(aa[i], bb[i]) * r;
	}
	head = cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt >= 2)
			if (bad(i, qu[head], qu[head + 1]) || bad(qu[head + cnt - 2], qu[head + cnt - 1], i))
				return 0;
			else if (!check(qu[head + cnt - 2], qu[head + cnt - 1], i))
				cnt--;
			else if (!check(i, qu[head], qu[head + 1]))
				head++, cnt--;
			else
				break;
		qu[head + cnt++] = i;
	}
	for (h = 0; h < cnt; h++)
		intersect(qu[head + h], qu[head + (h + 1) % cnt], &xx_[h], &yy_[h]);
	for (h = 0, h_ = 1; h < cnt; h++) {
		while (cross2(xx_[(h + 1) % cnt] - xx_[h], yy_[(h + 1) % cnt] - yy_[h], xx_[(h_ + 1) % cnt] - xx_[h_], yy_[(h_ + 1) % cnt] - yy_[h_]) > 0)
			h_ = (h_ + 1) % cnt;
		if (dot2(xx_[h_] - xx_[h], yy_[h_] - yy_[h], xx_[h_] - xx_[h], yy_[h_] - yy_[h]) >= r * r * 4)
			return 1;
	}
	return 0;
}

int main() {
	static int xx_[N], yy_[N];
	int n_, i;
	ld lower, upper;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (cross(xx[(i - 1 + n) % n], yy[(i - 1 + n) % n], xx[i], yy[i], xx[(i + 1) % n], yy[(i + 1) % n]) != 0)
			xx_[n_] = xx[i], yy_[n_] = yy[i], n_++;
	for (i = 0; i < n_; i++)
		xx[i] = xx_[i], yy[i] = yy_[i];
	n = n_;
	lower = 0, upper = 1e9;
	while (upper - lower > 1e-4) {
		ld r = (lower + upper) / 2;

		if (solve(r))
			lower = r;
		else
			upper = r;
	}
	printf("%.3Lf\n", lower);
	return 0;
}

Compilation message (stderr)

twocircles.cpp: In function 'int check_(int, int)':
twocircles.cpp:32:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   32 |  if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
      |                   ~~~~~~~~~~~^~~~~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
twocircles.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100