Submission #119698

# Submission time Handle Problem Language Result Execution time Memory
119698 2019-06-21T22:44:41 Z tutis 2circles (balkan11_2circles) C++17
10 / 100
4000 ms 65536 KB
/*input
6
0 0
8 0
8 6
4 8
2 8
0 4
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct point
{
	ld x, y;
	point() {}
	point(ld x, ld y): x(x), y(y) {}
	ld r()
	{
		return sqrtl(x * x + y * y);
	}
};
point operator+(const point &a, const point &b)
{
	return point(a.x + b.x, a.y + b.y);
}
point operator-(const point &a, const point &b)
{
	return point(a.x - b.x, a.y - b.y);
}
point operator*(const point &a, const point &b)
{
	return point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
point operator*(point a, ld k)
{
	return point(a.x * k, a.y * k);
}
ld dot(const point &a, const point &b)
{
	return a.x * b.x + a.y * b.y;
}
ld cross(const point &a, const point &b)
{
	return a.x * b.y - a.y * b.x;
}
point x(const point &a, point b, const point &c, point d)
{
	b = b - a;
	d = d - c;
	ld y = cross(a - c, b) / cross(d, b);
	return c + d * y;
}
struct line
{
	point a, b;
};
point x(const line &a, const line &b)
{
	return x(a.a, a.b, b.a, b.b);
}
int n;
point A[50505];
bool nereik(line a, line b, line c)
{
	return cross(x(a, c) - b.a, b.b - b.a) > 0;
}
deque<line> taisom(deque<line>a)
{
	if (a.size() <= 2)
		return {};
	for (int i = 0; i < (int)a.size(); i++)
	{
		int j = (i + 1)%a.size();
		int k = (i + 2)%a.size();
		if (cross(a[i].b - a[i].a, a[k].b - a[k].a) > 1e-8)
		{
			if (nereik(a[i], a[j], a[k]))
			{
				a.erase(a.begin() + j);
				return taisom(a);
			}
		}
		else
		{
			if (cross(a[k].a - a[i].a, a[i].b - a[i].a) > 0)
				return {};
		}
	}
	return a;
}
deque<point>x(deque<line>a)
{
	deque<point>ret;
	for (int i = 0; i < (int)a.size(); i++)
	{
		ret.push_back(x(a[i], a[(i + 1) % a.size()]));
	}
	return ret;
}
ld maxi(const deque<point> &a)
{
	ld ret = 0;
	for (int i = 0; i < (int)a.size(); i++)
	{
		for (int j = 0; j < i; j++)
		{
			ret = max(ret, (a[i] - a[j]).r());
		}
	}
	return ret;
}
bool ok(ld r)
{
	deque<line>tieses;
	for (int i = 0; i < n; i++)
	{
		point v = (A[i + 1] - A[i]) * point(0, 1);
		v = v * (r / v.r());
		tieses.push_back(line());
		tieses.back().a = A[i] + v;
		tieses.back().b = A[i + 1] + v;
	}
	return maxi(x(taisom(tieses))) >= 2 * r;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i].x >> A[i].y;
	A[n] = A[0];
	ld lo = 0;
	ld hi = 3e7;
	for (int t = 0; t < 100; t++)
	{
		ld r = (lo + hi) / 2;
		if (ok(r))
			lo = r;
		else
			hi = r;
	}
	ld r = (lo + hi) / 2;
	cout << fixed << setprecision(15) << r << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 18 ms 384 KB Output isn't correct
4 Incorrect 33 ms 512 KB Output isn't correct
5 Runtime error 92 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 4026 ms 5276 KB Time limit exceeded
7 Runtime error 71 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 70 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 82 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 90 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)