QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387595 | #5479. Traveling Salesperson in an Island | ucup-team1209 | WA | 1ms | 3984kb | C++20 | 2.8kb | 2024-04-12 17:13:05 | 2024-04-12 17:13:05 |
Judging History
answer
#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 205;
struct p2 {
db x, y;
db abs() const {
return std::sqrt(norm());
}
ll norm() const {
return (ll) x * x + (ll) y * y;
}
};
p2 operator + (p2 x, p2 y) { return {x.x + y.x, x.y + y.y}; }
p2 operator - (p2 x, p2 y) { return {x.x - y.x, x.y - y.y}; }
ll operator * (p2 x, p2 y) { return (ll) x.x * y.y - (ll) x.y * y.x; }
ll operator % (p2 x, p2 y) { return (ll) x.x * y.x + (ll) x.y * y.y; }
p2 operator * (p2 x, db y) { return {x.x * y, x.y * y}; }
int sgn(ll x) {
return x < 0 ? -1 : x > 0;
}
const db inf = 1e8;
const db eps = 1e-8;
bool contains(p2 x, p2 y, const std::vector<p2> & a) {
using pr = std::pair<double, int>;
std::vector<pr> e = {pr(-inf, 0), pr(inf, 0)};
p2 t = y - x;
auto f = [&](p2 a, p2 b, p2 c, p2 d) {
return (b - a).abs() * ((c - a) * (d - c)) / ((b - a) * (d - c));
};
for(int i = 0;i < (int) a.size();++i) {
p2 u = a[i], v = a[(i + 1) % a.size()];
int a = sgn(t * (u - x));
int b = sgn(t * (v - x));
if(a != b) e.emplace_back(f(x, y, u, v), b - a);
}
sort(e.begin(), e.end());
int sum = 0;
db R = t.abs();
for(int i = 0;i + 1 < (int) e.size();++i) {
sum += e[i].second;
if(sum == 0) {
if(std::max<db>(e[i].first, 0) + eps < std::min<db>(e[i + 1].first, R)) {
return 0;
}
}
}
return 1;
}
p2 a[N];
int n, m;
db d[N][N];
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for(int i = 0;i < n + m;++i) {
cin >> a[i].x >> a[i].y;
}
std::vector<int> idx(m);
std::vector<db> dist(m);
for(int i = 0;i < m;++i) {
p2 z = a[i + n];
for(int j = 0;j < n;++j) {
p2 A = a[j], B = a[(j + 1) % n];
if((z - A) * (z - B) == 0 && (z - A) % (z - B) <= 0) {
idx[i] = j;
dist[i] = (z - A).abs();
}
}
}
std::vector<int> rk(m);
for(int i = 0;i < m;++i) {
rk[i] = i;
}
sort(rk.begin(), rk.end(), [&](int x, int y) {
if(idx[x] != idx[y]) {
return idx[x] < idx[y];
}
return dist[x] < dist[y];
});
std::vector<p2> P(a, a + n);
for(int i = 0;i < n + m;++i) {
for(int j = 0;j < n + m;++j) {
const int C = 5;
p2 z[C + 1];
int ok = 1;
for(int x = 0;x <= C;++x) {
z[x] = (a[i] * db(C - x) + a[j] * (db)x) * (1. / C);
}
for(int i = 0;i < C;++i) {
ok = ok && contains(z[i], z[i + 1], P);
}
if(ok) {
d[i][j] = (a[i] - a[j]).abs();
} else {
d[i][j] = 1e18;
}
}
}
for(int i = 0;i < n + m;++i) {
for(int j = 0;j < n + m;++j) {
for(int k = 0;k < n + m;++k) {
d[j][k] = std::min(d[j][k], d[j][i] + d[i][k]);
}
}
}
db ans = 0;
for(int i = 0;i < m;++i) {
ans += d[n + rk[i]][n + rk[(i + 1) % m]];
}
printf("%.20lf\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3984kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.65685424949238058190
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3920kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
8.00000000000000000000
result:
wrong answer 1st numbers differ - expected: '16.6491106', found: '8.0000000', error = '0.5194939'