Submission #223883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223883	2020-04-16T19:48:24 Z	dolphingarlic	2circles (balkan11_2circles)	C++14	100 / 100	145 ms	2552 KB

twocircles

#include <bits/stdc++.h>
using namespace std;

const double PI = 4 * atan(1);

struct Point {
	double x, y;
} p[100001], d[100001];

int n;

bool ccw(Point X, Point Y, Point Z) {
	return (X.x - Y.x) * (Z.y - Y.y) <= (X.y - Y.y) * (Z.x - Y.x);
}

Point intersect(Point A, Point B, Point C, Point D) {
	double t = (-(A.y - B.y) * (D.x - B.x) + (A.x - B.x) * (D.y - B.y)) / ((A.y - B.y) * (C.x - D.x) - (A.x - B.x) * (C.y - D.y));
	return {t * C.x + (1 - t) * D.x, t * C.y + (1 - t) * D.y};
}

bool check(double r) {
	int h = 1, t = 0;

	for (int i = 0; i < n; i++) {
		double dx = -(p[i + 1].y - p[i].y), dy = p[i + 1].x - p[i].x;
		double l = hypot(dx, dy);
		dx = dx * r / l, dy = dy * r / l;

		Point A = {p[i].x + dx + (p[i].x - p[i + 1].x) * 1e5, p[i].y + dy + (p[i].y - p[i + 1].y) * 1e5};
		Point B = {p[i + 1].x + dx + (p[i + 1].x - p[i].x) * 1e5, p[i + 1].y + dy + (p[i + 1].y - p[i].y) * 1e5};

		if (!i) {
			d[++t] = A;
			d[++t] = B;
			continue;
		}

		if (!ccw(A, B, d[t])) {
			while (h <= t && !ccw(A, B, d[t])) t--;
			if (h > t) return false;
			d[t + 1] = intersect(d[t], d[t + 1], A, B);
			t++;
		}
		if (!ccw(A, B, d[h])) {
			while (h <= t && !ccw(A, B, d[h])) h++;
			d[h - 1] = intersect(d[h - 1], d[h], A, B);
			h--;
			d[++t] = d[h];
		} else d[++t] = B;
	}

	int c = h + 1;
	for (int i = h; i < t; i++) {
		while (hypot(d[i].x - d[c].x, d[i].y - d[c].y) < hypot(d[i].x - d[c + 1].x, d[i].y - d[c + 1].y)) {
			c++;
			if (c == t) c = h;
		}
		if (hypot(d[i].x - d[c].x, d[i].y - d[c].y) >= 2 * r) return true;
	}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
	p[n] = p[0];

	double area = 0;
	for (int i = 0; i < n; i++) area += p[i].x * p[i + 1].y - p[i].y * p[i + 1].x;
	if (area < 0) area = -area;
	area /= 2;

	double l = 0, r = sqrt(area / (2 * PI));
	while (r - l > 1e-4) {
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	printf("%.3lf\n", l);
	return 0;
}

Compilation message

twocircles.cpp: In function 'int main()':
twocircles.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
twocircles.cpp:65:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	9 ms	512 KB	Output is correct
6	Correct	36 ms	768 KB	Output is correct
7	Correct	32 ms	768 KB	Output is correct
8	Correct	31 ms	1024 KB	Output is correct
9	Correct	88 ms	1664 KB	Output is correct
10	Correct	145 ms	2552 KB	Output is correct