| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 489649 | rainboy | Svjetlost (COI18_svjetlost) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <math.h>
#include <stdio.h>
#define N 100000
double hypot(double x, double y) { return sqrt(x * x + y * y); }
double max(double a, double b) { return a > b ? a : b; }
int xx[N], yy[N], n; char dead[N];
long long cross(int x1, int y1, int x2, int y2) {
return (long long) x1 * y2 - (long long) x2 * y1;
}
long long dot(int x1, int y1, int x2, int y2) {
return (long long) x1 * x2 + (long long) y1 * y2;
}
int check(int x1, int y1, int x2, int y2) {
long long c = cross(x1, y1, x2, y2);
return c != 0 ? c > 0 : dot(x1, y1, x2, y2) > 0;
}
double solve() {
static int ii[N];
int h, h_, i, cnt;
double d, d_;
cnt = 0;
for (i = 0; i < n; i++)
if (!dead[i])
ii[cnt++] = i;
d = 0, d_ = 0;
for (h = 0, h_ = 0; h < cnt; h++) {
while (check(xx[ii[(h + 1) % cnt]] - xx[ii[h]], yy[ii[(h + 1) % cnt]] - yy[ii[h]], xx[ii[(h_ + 1) % cnt]] - xx[ii[h_]], yy[ii[(h_ + 1) % cnt]] - yy[ii[h_]])) {
d += hypot(xx[ii[(h_ + 1) % cnt]] - xx[ii[h_]], yy[ii[(h_ + 1) % cnt]] - yy[ii[h_]]);
h_ = (h_ + 1) % cnt;
}
d_ = max(d_, d);
d -= hypot(xx[ii[(h + 1) % cnt]] - xx[ii[h]], yy[ii[(h + 1) % cnt]] - yy[ii[h]]);
}
return d_;
}
int main() {
int q, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
scanf("%d", &q);
printf("%f\n", solve());
while (q--) {
int i;
scanf("%d", &i), i--;
dead[i] = 1;
printf("%f\n", solve());
}
return 0;
}