/*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;
}
ld y(const point &a, point b, const point &c, point d)
{
b = b - a;
d = d - c;
return cross(a - c, b) / cross(d, b);
}
struct line
{
point a, b;
};
point x(const line &a, const line &b)
{
return x(a.a, a.b, b.a, b.b);
}
ld y(const line &a, const line &b)
{
return y(a.a, a.b, b.a, b.b);
}
int n;
point A[505050];
bool nereik(const line &a, const line &b, const line &c)
{
return y(a, b) >= y(c, b);
}
void taisom(list<line> &a)
{
if (a.size() <= 2)
{
a = {};
return;
}
int dar = a.size() + 10;
for (auto ii = a.begin(); dar > 0;)
{
if (a.size() <= 2)
{
a = {};
return;
}
auto jj = ii; jj++;
if (jj == a.end())jj = a.begin();
auto kk = jj; kk++;
if (kk == a.end())kk = a.begin();
auto zz = ii;
if (zz != a.begin())
zz--;
else
zz = (--a.end());
if (abs(cross(zz->b - zz->a, jj->b - jj->a)) > 0.5)
{
if (nereik(*zz, *ii, *jj))
{
a.erase(ii);
dar = a.size() + 10;
ii = zz;
continue;
}
}
else
{
if (cross(jj->a - zz->a, zz->b - zz->a) > 0)
{
a = {};
return;
}
}
if (abs(cross(ii->b - ii->a, kk->b - kk->a)) > 0.5)
{
if (nereik(*ii, *jj, *kk))
{
a.erase(jj);
dar = a.size() + 10;
continue;
}
}
else
{
if (cross(kk->a - ii->a, ii->b - ii->a) > 0)
{
a = {};
return;
}
}
ii++;
dar--;
if (ii == a.end())
ii = a.begin();
}
}
vector<point>x(vector<line>a)
{
vector<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(vector<point> a, ld r)
{
int n = a.size();
if (n <= 2)
return false;
a.push_back(a[0]);
int j = 1;
for (int i = 0; i < n; i++)
{
while (true)
{
if ((a[j] - a[i]).r() >= r)
return true;
if ((a[j] - a[i + 1]).r() >= r)
return true;
int j_ = (j + 1) % n;
if (abs(cross(a[j_] - a[i], a[i] - a[i + 1])) >=
abs(cross(a[j] - a[i], a[i] - a[i + 1])))
j = j_;
else
break;
}
if ((a[j] - a[i]).r() >= r)
return true;
if ((a[j] - a[i + 1]).r() >= r)
return true;
}
return false;
}
bool ok(ld r)
{
list<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;
}
taisom(tieses);
vector<line>z(tieses.begin(), tieses.end());
return maxi(x(z), 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 = 4e7;
for (int t = 0; t < 40; 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 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
19 ms |
896 KB |
Output is correct |
| 6 |
Correct |
134 ms |
3520 KB |
Output is correct |
| 7 |
Correct |
83 ms |
2944 KB |
Output is correct |
| 8 |
Correct |
83 ms |
2268 KB |
Output is correct |
| 9 |
Correct |
324 ms |
6708 KB |
Output is correct |
| 10 |
Correct |
589 ms |
10492 KB |
Output is correct |
