#include <math.h>
#include <stdio.h>
#define N 100000
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++) {
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;
}
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(xx_[(h + 1) % cnt] - xx_[h], yy_[(h + 1) % cnt] - yy_[h], xx_[(h_ + 1) % cnt] - xx_[h_], yy_[(h_ + 1) % cnt] - yy_[h_]) > 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);
return 0;
}
Compilation message
twocircles.cpp: In function 'int check_(int, int)':
twocircles.cpp:30:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
30 | if (aa[i] < 0 || aa[i] == 0 && bb[i] < 0)
| ~~~~~~~~~~~^~~~~~~~~~~~
twocircles.cpp: In function 'int main()':
twocircles.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
twocircles.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d%d", &xx[i], &yy[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
12 ms |
440 KB |
Output is correct |
| 6 |
Correct |
44 ms |
836 KB |
Output is correct |
| 7 |
Correct |
58 ms |
852 KB |
Output is correct |
| 8 |
Correct |
84 ms |
1056 KB |
Output is correct |
| 9 |
Incorrect |
140 ms |
1924 KB |
Output isn't correct |
| 10 |
Incorrect |
214 ms |
2964 KB |
Output isn't correct |
