#include <math.h>
#include <stdio.h>
#define N 50000
typedef long double ld;
ld cross2(ld x1, ld y1, ld x2, ld y2) {
return x1 * y2 - x2 * y1;
}
ld cross(ld x0, ld y0, ld x1, ld y1, ld x2, ld y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
ld dot2(ld x1, ld y1, ld x2, ld y2) {
return x1 * x2 + y1 * y2;
}
int xx[N], yy[N], n;
ld aa[N], bb[N], cc[N];
void intersect(int i, int j, ld *x, ld *y) {
ld u = cross2(cc[i], bb[i], cc[j], bb[j]);
ld v = cross2(aa[i], cc[i], aa[j], cc[j]);
ld w = cross2(aa[i], bb[i], aa[j], bb[j]);
*x = u / w, *y = v / w;
}
int check_(int i, int j) {
if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
return check_(j, i);
if (aa[i] != 0)
return cross2(aa[i], cc[i], aa[j], cc[j]) < 0;
else
return cross2(bb[i], cc[i], bb[j], cc[j]) < 0;
}
int check(int i, int j, int k) {
ld x1, y1, x2, y2;
if (cross2(aa[i], bb[i], aa[j], bb[j]) == 0 && !check_(i, j))
return 0;
if (cross2(aa[j], bb[j], aa[k], bb[k]) == 0 && !check_(j, k))
return 0;
if (cross2(aa[i], bb[i], aa[j], bb[j]) <= 0 || cross2(aa[j], bb[j], aa[k], bb[k]) <= 0)
return 1;
intersect(i, j, &x1, &y1), intersect(j, k, &x2, &y2);
return cross2(aa[j], bb[j], x2 - x1, y2 - y1) < 0;
}
int bad(int i, int j, int k) {
return !check(i, j, k) && !check(j, k, i) && !check(k, i, j);
}
int solve(ld r) {
static int qu[N];
static ld xx_[N], yy_[N];
int h, h_, i, j, head, cnt;
for (i = 0; i < n; i++) {
j = (i + 1) % n;
aa[i] = yy[i] - yy[j];
bb[i] = xx[j] - xx[i];
cc[i] = dot2(aa[i], bb[i], xx[i], yy[i]) + hypotl(aa[i], bb[i]) * r;
}
head = cnt = 0;
for (i = 0; i < n; i++) {
while (cnt >= 2)
if (bad(i, qu[head], qu[head + 1]) || bad(qu[head + cnt - 2], qu[head + cnt - 1], i))
return 0;
else if (!check(qu[head + cnt - 2], qu[head + cnt - 1], i))
cnt--;
else if (!check(i, qu[head], qu[head + 1]))
head++, cnt--;
else
break;
qu[head + cnt++] = i;
}
if (cnt <= 2)
return 0;
for (h = 0; h < cnt; h++)
intersect(qu[head + h], qu[head + (h + 1) % cnt], &xx_[h], &yy_[h]);
for (h = 0, h_ = 1; h < cnt; h++) {
while (cross2(aa[qu[head + (h + 1) % cnt]], bb[qu[head + (h + 1) % cnt]], aa[qu[head + (h_ + 1) % cnt]], bb[qu[head + (h_ + 1) % cnt]]) > 0)
h_ = (h_ + 1) % cnt;
if (dot2(xx_[h_] - xx_[h], yy_[h_] - yy_[h], xx_[h_] - xx_[h], yy_[h_] - yy_[h]) >= r * r * 4)
return 1;
}
return 0;
}
int main() {
static int xx_[N], yy_[N];
int n_, i;
ld lower, upper;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
n_ = 0;
for (i = 0; i < n; i++)
if (cross(xx[(i - 1 + n) % n], yy[(i - 1 + n) % n], xx[i], yy[i], xx[(i + 1) % n], yy[(i + 1) % n]) != 0)
xx_[n_] = xx[i], yy_[n_] = yy[i], n_++;
for (i = 0; i < n_; i++)
xx[i] = xx_[i], yy[i] = yy_[i];
n = n_;
lower = 0, upper = 1e9;
while (upper - lower > 1e-4) {
ld r = (lower + upper) / 2;
if (solve(r))
lower = r;
else
upper = r;
}
printf("%.3Lf\n", lower);
return 0;
}
Compilation message
twocircles.cpp: In function 'int check_(int, int)':
twocircles.cpp:32:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
32 | if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
| ~~~~~~~~~~~^~~~~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
twocircles.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d", &xx[i], &yy[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
4 ms |
340 KB |
Output is correct |
| 5 |
Correct |
35 ms |
484 KB |
Output is correct |
| 6 |
Correct |
130 ms |
1336 KB |
Output is correct |
| 7 |
Correct |
179 ms |
1388 KB |
Output is correct |
| 8 |
Correct |
261 ms |
1496 KB |
Output is correct |
| 9 |
Correct |
432 ms |
2984 KB |
Output is correct |
| 10 |
Incorrect |
682 ms |
4696 KB |
Output isn't correct |
