Submission #223886

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223886	2020-04-16T19:54:30 Z	dolphingarlic	2circles (balkan11_2circles)	C++14	100 / 100	144 ms	1792 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;
 
	double l = 0, r = sqrt(area / 4 / 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:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
twocircles.cpp:63: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	5 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	384 KB	Output is correct
6	Correct	37 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	88 ms	1152 KB	Output is correct
10	Correct	144 ms	1792 KB	Output is correct