Youthful-Passion-Fruit-teambook
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub AlexanderNekrasov/Youthful-Passion-Fruit-teambook
verify/geometry/igor-tests/20.cpp
- View this file on GitHub
- Last update: 2024-08-11 10:07:38+00:00
- Link: https://codeforces.com/gym/104011/problem/G
Depends on
- contest/template.cpp
- geometry/Intersections.cpp
- geometry/IsHpiEmpty.cpp
- geometry/Line.cpp
- geometry/Point.cpp
Verified with
Code
// 2021-2022 ICPC NERC (NEERC), North-Western Russia Regional Contest
// (Northern Subregionals) G https://codeforces.com/gym/104011/problem/G
#define main main2
#include "../../../contest/template.cpp"
#undef main
#include "../../../geometry/Point.cpp"
#include "../../../geometry/Line.cpp"
#include "../../../geometry/Intersections.cpp"
#include "../../../geometry/IsHpiEmpty.cpp"
int main() {
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
int pos = min_element(all(p)) - p.begin();
rotate(p.begin(), p.begin() + pos, p.end());
vector<point> v;
for (int i = 0; i < n; ++i) {
v.push_back(p[i + 1 < n ? i + 1 : 0] - p[i]);
}
vector<int> fpos(n);
for (int i = 0; i < n; ++i) {
int pos = lower_bound(all(v), point{0,0} - v[i], cmpHalf) - v.begin();
pos = pos % n;
fpos[i] = pos;
}
auto check = [&](ld x) -> bool {
vector<line> lines;
lines.reserve(2 * n);
auto addLine = [&](int i, int j) {
vec v1 = (p[j] - p[i]) * (x / (x + 1));
vec v2 = (p[j + 1 < n ? j + 1 : 0] - p[i]) * (x / (x + 1));
lines.push_back(getln(p[i] + v1, p[i] + v2));
};
for (int i = 0; i < n; ++i) {
int pos = fpos[i];
addLine(i, pos);
addLine(pos, i);
}
return !isHpiEmpty(lines);
};
ld L = 1, R = 2;
for (int it = 0; it < 19; ++it) {
ld M = sqrt(L * R);
if (check(M)) {
R = M;
} else {
L = M;
}
}
cout << sqrt(L * R) << endl;
}#line 1 "verify/geometry/igor-tests/20.cpp"
// 2021-2022 ICPC NERC (NEERC), North-Western Russia Regional Contest
// (Northern Subregionals) G https://codeforces.com/gym/104011/problem/G
#define main main2
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define pbc push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define vin(v) for (auto &el : a) cin >> el
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 &y) {
if (y < x) {
x = y;
}
}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 &y) {
if (x < y) {
x = y;
}
}
void solve() {
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
#line 5 "verify/geometry/igor-tests/20.cpp"
#undef main
#line 1 "geometry/Point.cpp"
/**
* Author: alexxela12345,daubi,talant
* Date: 2024-08-03
* Description: struct Point
*/
const ld EPS = 1e-7;
ld sq(ld x) {
return x * x;
}
int sign(ld x) {
if (x < -EPS) {
return -1;
}
if (x > EPS) {
return 1;
}
return 0;
}
#define vec point
struct point {//% - cross, * - dot
ld x, y;
auto operator<=>(const point&) const = default;
};
ld operator*(const point &a, const point &b) {
return a.x * b.x + a.y * b.y;
}
ld operator%(const point &a, const point &b) {
return a.x * b.y - a.y * b.x;
}
point operator-(const point &a, const point &b) {
return {a.x - b.x, a.y - b.y};
}
point operator+(const point &a, const point &b) {
return {a.x + b.x, a.y + b.y};
}
point operator*(const point &a, ld b) {
return {a.x * b, a.y * b};
}
point operator/(const point &a, ld b) {
return {a.x / b, a.y / b};
}
bool operator<(const point &a, const point &b) {
if (sign(a.y - b.y) != 0) {
return a.y < b.y;
} else if (sign(a.x - b.x) != 0) {
return a.x < b.x;
}
return 0;
}
ld len2(const point &a) {
return sq(a.x) + sq(a.y);
}
ld len(const point &a) {
return sqrt(len2(a));
}
point norm(point a) {
return a / len(a);
}
int half(point a) {
return (sign(a.y) == -1 || (sign(a.y) ==0 && a.x < 0));
}
point ort(point a) {
return {-a.y, a.x};
}
point turn(point a, ld ang) {
return {a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang)};
}
ld getAngle(point &a, point &b) {
return atan2(a % b, a * b);
}
bool cmpHalf(const point &a, const point &b) {
if (half(a) != half(b)) {
return half(b);
} else {
int sgn = sign(a % b);
if (!sgn) {
return len2(a) < len2(b);
} else {
return sgn == 1;
}
}
}
#line 1 "geometry/Line.cpp"
/**
* Author: alexxela12345,daubi,talant
* Date: 2024-08-03
* Description: struct Line
*/
struct line {
ld a, b, c;
void norm() {
// for half planes
ld d = len({a, b});
assert(sign(d) > 0);
a /= d;
b /= d;
c /= d;
}
ld eval(point p) const { return a * p.x + b * p.y + c; }
bool isIn(point p) const { return sign(eval(p)) >= 0; }
bool operator==(const line &other) const {
return sign(a * other.b - b * other.a) == 0 &&
sign(a * other.c - c * other.a) == 0 &&
sign(b * other.c - c * other.b) == 0;
}
};
line getln(point a, point b) {
line res;
res.a = a.y - b.y;
res.b = b.x - a.x;
res.c = -(res.a * a.x + res.b * a.y);
res.norm();
return res;
}
#line 1 "geometry/Intersections.cpp"
/**
* Author: alexxela12345,daubi,talant
* Date: 2024-08-03
* Description: Geometry intersections
*/
bool isCrossed(ld lx, ld rx, ld ly, ld ry) {
if (lx > rx)
swap(lx, rx);
if (ly > ry)
swap(ly, ry);
return sign(min(rx, ry) - max(lx, ly)) >= 0;
}
// if two segments [a, b] and [c, d] has AT LEAST one common point -> true
bool intersects(const point &a, const point &b, const point &c, const point &d) {
if (!isCrossed(a.x, b.x, c.x, d.x))
return false;
if (!isCrossed(a.y, b.y, c.y, d.y))
return false;
if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) == 1) return 0;
if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) == 1) return 0;
return 1;
}
//intersecting lines
bool intersect(line l, line m, point &I) {
ld d = l.b * m.a - m.b * l.a;
if (sign(d) == 0) {
return false;
}
ld dx = m.b * l.c - m.c * l.b;
ld dy = m.c * l.a - l.c * m.a;
I = {dx / d, dy / d};
return true;
}
//intersecting circles
int intersect(point o1, ld r1, point o2, ld r2, point &i1, point &i2) {
if (r1 < r2) {
swap(o1, o2);
swap(r1, r2);
}
if (sign(r1 - r2) == 0 && len2(o2 - o1) < EPS) {
return 3;
}
ld ln = len(o1 - o2);
if (sign(ln - r1 - r2) == 1 || sign(r1 - ln - r2) == 1) {
return 0;
}
ld d = (sq(r1) - sq(r2) + sq(ln)) / 2 / ln;
vec v = norm(o2 - o1);
point a = o1 + v * d;
if (sign(ln - r1 - r2) == 0 || sign(ln + r2 - r1) == 0) {
i1 = a;
return 1;
}
v = ort(v) * sqrt(sq(r1) - sq(d));
i1 = a + v;
i2 = a - v;
return 2;
}
//intersecting line and circle, line should be normed
int intersect(point o, ld r, line l, point &i1, point &i2) {
ld len = abs(l.eval(o));
int sgn = sign(len - r);
if (sgn == 1) {
return 0;
}
vec v = norm(vec{l.a, l.b}) * len;
if (sign(l.eval(o + v)) != 0) {
v = vec{0, 0} - v;
}
point a = o + v;
if (sgn == 0) {
i1 = a;
return 1;
}
v = norm({-l.b, l.a}) * sqrt(sq(r) - sq(len));
i1 = a + v;
i2 = a - v;
return 2;
}
#line 1 "geometry/IsHpiEmpty.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Determines is half plane intersectinos.
* Time: O(n) (expected)
*/
// all lines must be normed!!!!!, sign > 0
bool isHpiEmpty(vector<line> lines) {
// return hpi(lines).empty();
// overflow/precision problems?
shuffle(all(lines), rnd);
const ld C = 1e9;
point ans(C, C);
vector<point> box = {{-C, -C}, {C, -C}, {C, C}, {-C, C}};
for (int i = 0; i < 4; ++i)
lines.push_back(getln(box[i], box[(i + 1) % 4]));
int n = lines.size();
for (int i = n - 4; i >= 0; --i) {
if (lines[i].isIn(ans))
continue;
point up(0, C + 1), down(0, -C - 1), pi = {lines[i].b, -lines[i].a};
for (int j = i + 1; j < n; ++j) {
if (lines[i] == lines[j])
continue;
point p, pj = {lines[j].b, -lines[j].a};
if (!intersect(lines[i], lines[j], p)) {
if (sign(pi * pj) != -1)
continue;
if (sign(lines[i].c + lines[j].c) *
(!sign(pi.y) ? sign(pi.x) : -1) ==
1)
return true;
} else {
if ((!sign(pi.y) ? sign(pi.x) : sign(pi.y)) * (sign(pi % pj)) ==
1)
chkmin(up, p);
else
chkmax(down, p);
}
}
if ((ans = up) < down)
return true;
}
// for (int i = 0; i < n; ++i) {
// assert(lines[i].eval(ans) < EPS);
// }
return false;
}
#line 11 "verify/geometry/igor-tests/20.cpp"
int main() {
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
int pos = min_element(all(p)) - p.begin();
rotate(p.begin(), p.begin() + pos, p.end());
vector<point> v;
for (int i = 0; i < n; ++i) {
v.push_back(p[i + 1 < n ? i + 1 : 0] - p[i]);
}
vector<int> fpos(n);
for (int i = 0; i < n; ++i) {
int pos = lower_bound(all(v), point{0,0} - v[i], cmpHalf) - v.begin();
pos = pos % n;
fpos[i] = pos;
}
auto check = [&](ld x) -> bool {
vector<line> lines;
lines.reserve(2 * n);
auto addLine = [&](int i, int j) {
vec v1 = (p[j] - p[i]) * (x / (x + 1));
vec v2 = (p[j + 1 < n ? j + 1 : 0] - p[i]) * (x / (x + 1));
lines.push_back(getln(p[i] + v1, p[i] + v2));
};
for (int i = 0; i < n; ++i) {
int pos = fpos[i];
addLine(i, pos);
addLine(pos, i);
}
return !isHpiEmpty(lines);
};
ld L = 1, R = 2;
for (int it = 0; it < 19; ++it) {
ld M = sqrt(L * R);
if (check(M)) {
R = M;
} else {
L = M;
}
}
cout << sqrt(L * R) << endl;
}