QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387584 | #5479. Traveling Salesperson in an Island | ucup-team1209 | RE | 0ms | 4016kb | C++20 | 2.6kb | 2024-04-12 17:03:36 | 2024-04-12 17:03:36 |
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 {
int 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; }
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[j] = (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) {
if(contains(a[i], a[j], P)) {
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: 0ms
memory: 4016kb
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
Runtime Error
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4