#include <math.h>
#include <stdio.h>
#define N 50000
double cross2(double x1, double y1, double x2, double y2) {
return x1 * y2 - x2 * y1;
}
double cross(double x0, double y0, double x1, double y1, double x2, double y2) {
return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}
double dot2(double x1, double y1, double x2, double y2) {
return x1 * x2 + y1 * y2;
}
int xx[N], yy[N], n;
double aa[N], bb[N], cc[N];
void intersect(int i, int j, double *x, double *y) {
double u = cross2(cc[i], bb[i], cc[j], bb[j]);
double v = cross2(aa[i], cc[i], aa[j], cc[j]);
double 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) {
double 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(double r) {
static int qu[N];
static double 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]) + hypot(aa[i], bb[i]) * r;
}
head = cnt = 0;
for (i = 0; i < n; i++) {
if (cnt && !check(qu[head + cnt - 1], i, qu[head]))
continue;
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 < cnt; h++)
if (cross(xx_[h], yy_[h], xx_[(h + 1) % cnt], yy_[(h + 1) % cnt], xx_[(h + 2) % cnt], yy_[(h + 2) % cnt]) <= 0)
return 0;
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;
double 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) {
double r = (lower + upper) / 2;
if (solve(r))
lower = r;
else
upper = r;
}
printf("%.3f\n", lower);
solve(lower);
return 0;
}
Compilation message
twocircles.c: In function 'check_':
twocircles.c:30:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
30 | if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
| ~~~~~~~~~~~^~~~~~~~~~~~
twocircles.c: In function 'main':
twocircles.c:102:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
twocircles.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc6HbK6Q.o: in function `solve':
twocircles.c:(.text+0x3fd): undefined reference to `hypot'
collect2: error: ld returned 1 exit status
