oj.uz

Submission #223890

# Submission time Handle Problem Language Result Execution time Memory
223890 2020-04-16T19:56:41 Z dolphingarlic 2circles (balkan11_2circles) C++14
100 / 100
 147 ms 1504 KB 
#include <bits/stdc++.h>
using namespace std;

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 l = 0, r = 1e7;
	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:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
twocircles.cpp:61: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 4 ms 384 KB Output is correct
2 Correct 4 ms 256 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 384 KB Output is correct
6 Correct 38 ms 640 KB Output is correct
7 Correct 33 ms 640 KB Output is correct
8 Correct 32 ms 768 KB Output is correct
9 Correct 96 ms 1024 KB Output is correct
10 Correct 147 ms 1504 KB Output is correct