#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair<ld, ld> pii;
ld inf = 1e9;
ld eps = 1e-8;
const int MAXN = 5e4;
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
ld cross(pii a, pii b) {
return a.first*b.second-a.second*b.first;
}
ld dot(pii a, pii b) {
return a.first*b.first+a.second*b.second;
}
pii operator-(pii a, pii b) {
return pii(a.first-b.first, a.second-b.second);
}
pii operator*(pii a, ld b) {
return pii(a.first*b, a.second*b);
}
pii operator/(pii a, ld b) {
return a*(1/b);
}
pii operator*(ld b, pii a) {
return a*b;
}
pii operator-(pii a) {
return (-1)*a;
}
ld mag(pii a) {
return sqrt(dot(a, a));
}
class Line {
public:
pii start;
pii vec;
// ld rbound = inf;
ld lbound = -inf;
Line() {}
Line(pii a, pii b) {
start = a;
vec = (b-a)/mag(b-a);
}
Line(Line other, ld x) {
vec = other.vec;
start = other.start+x*pii(-vec.second, vec.first);
}
pii get_point() {
// assert(rbound < inf-eps);
return start+vec*lbound;
}
};
ld cross(Line a, Line b) {
return cross(a.vec, b.vec);
}
pii points[MAXN];
Line lines[MAXN];
Line lines_orig[MAXN];
pii points_temp[MAXN];
int n;
ld mx_dist(int f, int t) {
int s = f;
ld best = 0;
for (int i = f; i < t; i++) {
while (s < t-1 && mag(points_temp[i]-points_temp[s]) < mag(points_temp[i]-points_temp[s+1])) s++;
best = max(best, mag(points_temp[i]-points_temp[s]));
}
return best;
}
ld inter(Line a, Line b) { // distance in direction of vec from start of a
return cross(b.start-a.start, b.vec)/cross(a.vec, b.vec);
}
bool possible(ld cur) {
vector<int> hull;
hull.push_back(0);
for (int i = 1; i < n; i++) {
if (cross(lines[hull.back()], lines[i]) < eps) return 0;
while (hull.size() > 1 && cross(lines[i].vec, lines[hull.back()].get_point()-lines[i].start) < eps) {
hull.pop_back();
if (cross(lines[hull.back()], lines[i]) < eps) return 0;
}
lines[i].lbound = inter(lines[i], lines[hull.back()]);
hull.push_back(i);
} // now check collisions between front & back
int s = 0;
bool b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps;
bool b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps;
while (hull.size() > 3 && (b1 || b2)) {
if (b1) {
hull.pop_back();
}
if (b2) {
s++;
}
b1 = cross(lines[hull[s]].vec, lines[hull.back()].get_point()-lines[hull[s]].start) < eps;
b2 = cross(lines[hull.back()].vec, lines[hull[s+1]].get_point()-lines[hull.back()].start) < eps;
}
lines[hull[s]].lbound = inter(lines[hull[s]], lines[hull.back()]);
for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point();
return (mx_dist(s, hull.size()) > 2*cur);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) cin >> points[i].first >> points[i].second;
for (int i = 0; i < n; i++) {
lines_orig[i] = Line(points[i], points[(i+1)%n]);
}
ld mn = 0;
ld mx = 6e6;
for (int i = 0; i < 100; i++) {
ld cur = (mn+mx)/2;
for (int i = 0; i < n; i++) lines[i] = Line(lines_orig[i], cur);
if (possible(cur)) mn = cur;
else mx = cur;
}
cout << fixed << setprecision(3) << mn << "\n";
}
Compilation message
twocircles.cpp: In function 'bool possible(ld)':
twocircles.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int i = s; i < hull.size(); i++) points_temp[i] = lines[hull[i]].get_point();
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8164 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 5 |
Correct |
28 ms |
8232 KB |
Output is correct |
| 6 |
Correct |
92 ms |
8940 KB |
Output is correct |
| 7 |
Correct |
98 ms |
8876 KB |
Output is correct |
| 8 |
Correct |
141 ms |
9032 KB |
Output is correct |
| 9 |
Correct |
252 ms |
10648 KB |
Output is correct |
| 10 |
Correct |
412 ms |
12112 KB |
Output is correct |
