Submission #4720

#	Time	Username	Problem	Language	Result	Execution time	Memory
4720		ainta	2circles (balkan11_2circles)	C++98	100 / 100	99 ms	3476 KiB

twocircles

#include<stdio.h>
#include<math.h>
#define PI 3.14159
struct point{
	double x, y;
}w[100100], Deq[50100];
double S;
int n;
bool ccw(point p, point q, point r){
	return (q.x - p.x)*(r.y - p.y) - (q.y - p.y)*(r.x - p.x) > 0;
}
point inter(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));
	point R;
	R.x = t*c.x + (1 - t)*d.x;
	R.y = t*c.y + (1 - t)*d.y;
	return R;
}
double dis(point a, point b){
	return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}
bool IsPossible(double R){
	int i, h = 1, t = 0, ck = 0, pv;
	double dx, dy, L;
	point P1, P2;
	for (i = 0; i < n; i++){
		dx = -(w[i + 1].y - w[i].y);
		dy = w[i + 1].x - w[i].x;
		L = sqrt(dx*dx + dy*dy);
		dx = dx*R / L, dy = dy*R / L;
		P1.x = w[i].x + dx + (w[i].x - w[i + 1].x)*1e5, P1.y = w[i].y + dy + (w[i].y - w[i + 1].y)*1e5;
		P2.x = w[i + 1].x + dx + (w[i + 1].x - w[i].x)*1e5, P2.y = w[i + 1].y + dy + (w[i + 1].y - w[i].y)*1e5;
		if (i == 0){
			Deq[++t] = P1, Deq[++t] = P2;
			continue;
		}
		if (!ccw(P1, P2, Deq[t])){
			while (h <= t && !ccw(P1, P2, Deq[t]))t--;
			if (h > t)return false;
			Deq[t + 1] = inter(Deq[t], Deq[t + 1], P1, P2);
			t++;
		}
		if (!ccw(P1, P2, Deq[h])){
			while (h <= t && !ccw(P1, P2, Deq[h]))h++;
			Deq[h - 1] = inter(Deq[h - 1], Deq[h], P1, P2);
			h--;
			Deq[++t] = Deq[h];
		}
		else Deq[++t] = P2;
	}
	pv = h + 1;
	for (i = h; i < t; i++){
		while (dis(Deq[i], Deq[pv])<dis(Deq[i], Deq[pv + 1])){
			pv++;
			if (pv == t)pv = h;
		}
		if (sqrt(dis(Deq[i], Deq[pv])) >= 2*R)return true;
	}
	return false;
}
int main()
{
	int i;
	double B, E, R;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%lf%lf", &w[i].x, &w[i].y);
	w[n] = w[0];
	for (i = 0; i < n; i++)
		S += w[i].x*w[i + 1].y - w[i].y*w[i + 1].x;
	if (S < 0)S = -S;
	S /= 2;
	B = 0, E = sqrt(S / (2 * PI));
	while (E-B > 0.0001){
		R = (B + E)*0.5;
		if (IsPossible(R))B = R;
		else E = R;
	}
	printf("%.3lf\n", R);
}

Compilation message (stderr)

2circles.cpp: In function 'bool IsPossible(double)':
2circles.cpp:23:23: warning: unused variable 'ck' [-Wunused-variable]
  int i, h = 1, t = 0, ck = 0, pv;
                       ^
2circles.cpp: In function 'int main()':
2circles.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
2circles.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf", &w[i].x, &w[i].y);
                                    ^

• Subtask 1: 100 / 100