QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #326082 | #3184. Around the Track | crimson231 | WA | 2ms | 4012kb | C++20 | 8.1kb | 2024-02-12 10:33:04 | 2024-02-12 10:33:05 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>;
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ld TOL = 1e-8;
const ld INF = 1e17;
const int LEN = 50;
int N, M, t;
ld G[LEN << 1][LEN << 1];
ld COST[LEN << 1];
struct Info {
int i;
ld c;
bool operator < (const Info& x) const { return c > x.c; }
};
std::priority_queue<Info> Q;
ld dijkstra(int v, int g) {
for (int i = 0; i < LEN << 1; i++) COST[i] = INF;
Q.push({ v, 0 });
COST[v] = 0;
while (Q.size()) {
Info p = Q.top(); Q.pop();
if (p.c > COST[p.i]) continue;
for (int j = 0; j < t; j++) {
ld w = G[p.i][j];
if (w > 1e16) continue;
ld cost = p.c + w;
if (COST[j] > cost) {
COST[j] = cost;
Q.push({ j, cost });
}
}
}
return COST[g];
}
bool z(const ld& x) { return std::abs(x) < TOL; }
struct Pos {
ld x, y;
int i;
Pos(ld X = 0, ld Y = 0, int I = 0) : x(X), y(Y), i(I) {}
bool operator == (const Pos& p) const { return z(x - p.x) && z(y - p.y); }
bool operator < (const Pos& p) const { return z(x - p.x) ? y < p.y : x < p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y, i }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y, i }; }
Pos operator * (const ld& n) const { return { x * n, y * n, i }; }
Pos operator / (const ld& n) const { return { x / n, y / n, i }; }
ld operator * (const Pos& p) const { return { x * p.x + y * p.y }; }
ld operator / (const Pos& p) const { return { x * p.y - y * p.x }; }
Pos operator ~ () const { return { -y, x, i }; }
ld operator ! () const { return x * y; }
Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
Pos& operator *= (const ld& scale) { x *= scale; y *= scale; return *this; }
ld mag() const { return hypot(x, y); }
} inner[LEN], outer[LEN], nodes[LEN << 1];
std::vector<Pos> C, H;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) {
ld ret = cross(d1, d2, d3);
return z(ret) ? 0 : ret > 0 ? 1 : -1;
}
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) {
ld ret = dot(d1, d3, d2);
return !ccw(d1, d2, d3) && (ret > 0 || z(ret));
}
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) {
ld ret = dot(d1, d3, d2);
return !ccw(d1, d2, d3) && ret > 0;
}
bool inner_check(Pos H[], const int& sz, const Pos& p) {
int cnt = 0;
for (int i = 0; i < sz; i++) {
Pos cur = H[i], nxt = H[(i + 1) % sz];
if (on_seg_strong(cur, nxt, p)) return 1;
if (z(cur.y - nxt.y)) continue;
if (nxt.y < cur.y) std::swap(cur, nxt);
if (nxt.y - TOL < p.y || cur.y > p.y) continue;
cnt += ccw(cur, nxt, p) > 0;
}
return cnt & 1;
}
bool intersect(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2) {
bool f1 = ccw(s1, s2, d1) * ccw(s2, s1, d2) > 0;
bool f2 = ccw(d1, d2, s1) * ccw(d2, d1, s2) > 0;
//bool f3 = on_seg_strong(s1, s2, p1) ||
// on_seg_strong(s1, s2, p2) ||
// on_seg_strong(p1, p2, s1) ||
// on_seg_strong(p1, p2, s2);
return (f1 && f2);// || f3;
}
bool blocked(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2) {
bool f0 = intersect(s1, s2, d1, d2);
bool f4 = on_seg_weak(s1, s2, d1) || on_seg_weak(s1, s2, d2);
return f0 || f4;
}
bool blocked(Pos H[], const int& sz, const Pos& s1, const Pos& s2) {
for (int i = 0; i < sz; i++) if (blocked(s1, s2, H[i], H[(i + 1) % sz])) return 1;
return 0;
}
void monotone_chain(std::vector<Pos>& C, std::vector<Pos>& H) {
std::sort(C.begin(), C.end());
if (C.size() <= 2) {
for (const Pos& p : C) H.push_back(p);
return;
}
for (int i = 0; i < C.size(); i++) {
while (H.size() > 1 && (cross(H[H.size() - 2], H[H.size() - 1], C[i]) < 0 || z(cross(H[H.size() - 2], H[H.size() - 1], C[i])))) {
H.pop_back();
}
H.push_back(C[i]);
}
H.pop_back();
int s = H.size() + 1;
for (int i = C.size() - 1; i >= 0; i--) {
while (H.size() > s && (cross(H[H.size() - 2], H[H.size() - 1], C[i]) < 0 || z(cross(H[H.size() - 2], H[H.size() - 1], C[i])))) {
H.pop_back();
}
H.push_back(C[i]);
}
H.pop_back();
return;
}
void floyd_warshall() {
//for (int k = 0; k < t; k++) {
// for (int i = 0; i < t; i++) {
// for (int j = 0; j < t; j++) {
// G[i][j] = std::min(G[i][k] + G[k][j], G[i][j]);
// }
// }
//}
for (int k = 0; k < t; k++) {
for (int i = 0; i < t; i++) {
for (int j = i + 1; j < t; j++) {
if (k != i && k != j) {
G[i][j] = std::min(G[i][k] + G[k][j], G[i][j]);
G[j][i] = std::min(G[j][k] + G[k][i], G[j][i]);
}
}
}
}
return;
}
bool connectable(const int& i, const int& j) {
return !blocked(outer, M, nodes[i], nodes[j])
&& !blocked(inner, N, nodes[i], nodes[j])
&& inner_check(outer, M, (nodes[i] + nodes[j]) * .5)
&& !inner_check(inner, N, (nodes[i] + nodes[j]) * .5);
}
void init() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(9);
t = 0;
std::cin >> N;
for (int i = 0; i < N; i++) {
std::cin >> inner[i].x >> inner[i].y;
inner[i].i = t;
nodes[t] = inner[i];
t++;
}
std::cin >> M;
for (int j = 0; j < M; j++) {
std::cin >> outer[j].x >> outer[j].y;
outer[j].i = t;
nodes[t] = outer[j];
t++;
}
C.resize(N);
for (int i = 0; i < N; i++) C[i] = inner[i];
monotone_chain(C, H);
return;
}
void solve() {
Pos seg;
for (int i = 0; i < t; i++) for (int j = 0; j < t; j++) G[i][j] = INF;
for (int i = 0; i < N; i++) {
G[i][(i + 1) % N] = (inner[i] - inner[(i + 1) % N]).mag();
for (int k = 0; k < t; k++) {
if (ccw(inner[i], inner[(i + 1) % N], nodes[k]) > 0 && connectable((i + 1) % N, k)) {
G[(i + 1) % N][k] = (inner[(i + 1) % N] - nodes[k]).mag();
}
}
}
for (int j = 0; j < M; j++) {
G[j + N][((j + 1) % M) + N] = (outer[j] - outer[(j + 1) % M]).mag();
for (int k = 0; k < t; k++) {
if (ccw(outer[j], outer[(j + 1) % M], nodes[k]) < 0 && connectable(((j + 1) % M) + N, k)) {
G[((j + 1) % M) + N][k] = (outer[(j + 1) % M] - nodes[k]).mag();
}
}
for (int k = 0; k < M; k++) {
if (G[((j + 1) % M) + N][k + N] > 1e16 && dot(outer[j], outer[(j + 1) % M], outer[k]) < 0 && connectable(((j + 1) % M) + N, k + N)) {
G[((j + 1) % M) + N][k + N] = (outer[(j + 1) % M] - outer[k]).mag();
}
}
}
//floyd_warshall();
ld length = 0;
int sz = H.size();
int s = H[0].i, e = H[1].i;
ld a = dijkstra(s, e), b = dijkstra(e, s);
length = a + b;
std::cout << length << "\n";
return;
}
int main() { init(); solve(); return 0; }//boj10518
/*
8
1 1
15 1
15 7
14 7
14 2
2 2
2 7
1 7
15
0 0
16 0
16 8
13 8
12 4
11 6
10 3
9 6
8 5
7 6
6 3
5 6
4 4
3 8
0 8
43.6832385
7
1 1
5 1
5 19
4 2
3 18
2 2
1 19
9
0 0
6 0
6 20
5 20
4 3
3 19
2 3
1 20
0 20
102.129031841
4
-1000 -1000
0 0
1000 -1000
0 2000
8
1500 -1500
0 2500
-1500 -1500
-460 -730
-20 -510
0 -50
20 -510
460 -730
*/
//void solve() {
// Pos seg;
// for (int i = 0; i < t; i++) for (int j = 0; j < t; j++) G[i][j] = INF;
// for (int i = 0; i < N; i++) {
// G[i][(i + 1) % N] = (inner[i] - inner[(i + 1) % N]).mag();
// for (int k = 0; k < t; k++) {
// if (ccw(inner[i], inner[(i + 1) % N], nodes[k]) > 0 && connectable((i + 1) % N, k)) {
// G[(i + 1) % N][k] = (inner[(i + 1) % N] - nodes[k]).mag();
// }
// }
// }
// for (int j = 0; j < M; j++) {
// G[j + N][((j + 1) % M) + N] = (outer[j] - outer[(j + 1) % M]).mag();
// for (int k = 0; k < t; k++) {
// if (ccw(outer[j], outer[(j + 1) % M], nodes[k]) < 0 && connectable(((j + 1) % M) + N, k)) {
// G[((j + 1) % M) + N][k] = (outer[(j + 1) % M] - nodes[k]).mag();
// }
// }
// }
// floyd_warshall();
// int sz = H.size();
// ld length = 0;
// for (int i = 0; i < sz; i++) {
// Pos cur = H[i], nxt = H[(i + 1) % sz];
// if (!blocked(outer, M, cur, nxt)) length += (cur - nxt).mag();
// else length += G[cur.i][nxt.i];
// }
// std::cout << length << "\n";
// return;
//}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3960kb
input:
3 1 1 2 1 1 2 3 0 0 4 0 0 4
output:
3.414213562
result:
ok found '3.4142136', expected '3.4142136', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
5 1 1 5 1 5 5 3 3 1 5 4 0 0 6 0 6 6 0 6
output:
16.000000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
5 1 1 5 1 5 5 3 3 1 5 5 0 0 6 0 6 6 3 4 0 6
output:
16.472135955
result:
ok found '16.4721360', expected '16.4721360', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
5 2 2 6 2 6 6 4 4 2 6 4 0 0 8 0 8 8 0 8
output:
16.000000000
result:
ok found '16.0000000', expected '16.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
5 2 2 6 2 6 6 4 4 2 6 5 0 0 8 0 8 8 4 5 0 8
output:
16.472135955
result:
ok found '16.4721360', expected '16.4721360', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
12 1 1 1 4 -1 4 -1 1 -4 1 -4 -1 -1 -1 -1 -4 1 -4 1 -1 4 -1 4 1 12 2 2 2 5 -2 5 -2 2 -5 2 -5 -2 -2 -2 -2 -5 2 -5 2 -2 5 -2 5 2
output:
25.888543820
result:
ok found '25.8885438', expected '25.8885438', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4012kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 6 10 3 9 6 8 5 7 6 6 3 5 6 4 4 3 8 0 8
output:
43.683238506
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 8 10 3 9 8 8 5 7 8 6 3 5 8 4 4 3 8 0 8
output:
43.683238506
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
8 1 1 15 1 15 7 14 7 14 2 2 2 2 7 1 7 15 0 0 16 0 16 8 13 8 12 4 11 7 10 3 9 7 8 5 7 7 6 3 5 7 4 4 3 8 0 8
output:
43.683238506
result:
ok found '43.6832385', expected '43.6832385', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
12 1 1 10 1 10 6 9 6 9 2 6 2 6 4 5 4 5 2 2 2 2 6 1 6 12 0 0 11 0 11 7 8 7 8 3 7 3 7 5 4 5 4 3 3 3 3 7 0 7
output:
33.152982445
result:
ok found '33.1529824', expected '33.1529824', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
7 1 1 5 1 5 19 4 2 3 18 2 2 1 19 9 0 0 6 0 6 20 5 20 4 3 3 19 2 3 1 20 0 20
output:
102.129031841
result:
ok found '102.1290318', expected '102.1290318', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 16 0 0 13 0 13 9 4 9 4 4 5 4 5 8 10 8 10 3 9 3 9 7 6 7 6 3 3 3 3 6 0 6
output:
36.796691275
result:
ok found '36.7966913', expected '36.7966913', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
12 1 1 12 1 12 5 11 5 11 2 8 2 8 6 7 6 7 2 2 2 2 5 1 5 12 0 0 13 0 13 9 4 9 4 4 5 4 5 8 6 8 6 3 3 3 3 6 0 6
output:
33.521451263
result:
ok found '33.5214513', expected '33.5214513', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
8 1 3 4 2 4 1 5 4 6 4 3 5 3 6 2 3 4 0 0 7 0 7 7 0 7
output:
14.422205102
result:
ok found '14.4222051', expected '14.4222051', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
8 1 2 2 1 4 3 4 5 5 5 4 6 2 4 2 2 4 2 0 6 4 4 7 0 3
output:
12.957417329
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
8 2 2 4 2 6 4 5 5 5 4 3 4 1 2 2 1 4 3 0 7 4 4 6 0 2
output:
12.957417329
result:
ok found '12.9574173', expected '12.9574173', error '0.0000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
12 1 3 4 2 9 2 9 1 10 4 10 9 11 9 8 10 3 10 3 11 2 8 2 3 4 0 3 9 0 12 9 3 12
output:
33.045188695
result:
ok found '33.0451887', expected '33.0451887', error '0.0000000'
Test #18:
score: -100
Wrong Answer
time: 2ms
memory: 4008kb
input:
44 21 -7 21 5 20 5 20 -6 17 -6 17 4 16 4 16 -5 13 -5 13 3 12 3 12 -4 9 -4 9 2 8 2 8 -3 5 -3 5 1 4 1 4 -2 1 -2 1 0 -1 0 -1 -2 -4 -2 -4 1 -5 1 -5 -3 -8 -3 -8 2 -9 2 -9 -4 -12 -4 -12 3 -13 3 -13 -5 -16 -5 -16 4 -17 4 -17 -6 -20 -6 -20 5 -21 5 -21 -7 44 22 -8 22 6 19 6 19 -5 18 -5 18 5 15 5 15 -4 14 -4 ...
output:
164.088280432
result:
wrong answer 1st numbers differ - expected: '200.7120664', found: '164.0882804', error = '0.1824693'