QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#485713 | #5479. Traveling Salesperson in an Island | enwask | WA | 22ms | 4040kb | C++17 | 6.4kb | 2024-07-21 02:21:38 | 2024-07-21 02:21:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
template<class T>
int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
ld dist() const { return sqrtl((ld) dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
}
friend ostream &operator<<(ostream &os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
typedef Point<ll> P;
const ld inf = 1e18;
template<class P>
int sideOf(P s, P e, P p) {
auto cp = s.cross(e, p);
return (cp > 0) - (cp < 0);
}
template<class P>
bool doSegInter(P s1, P e1, P s2, P e2) {
return sideOf(s1, e1, s2) != sideOf(s1, e1, e2) && sideOf(s2, e2, s1) != sideOf(s2, e2, e1);
}
void solve() {
int n, m;
cin >> n >> m;
int k = n + m;
vector<P> pol(n), pts(m), all_pts(k);
vector<vi> lin(n); // points in pts on the line from pol[i] to pol[(i+1)%n], sorted by distance from pol[i]
vector<set<int>> on_lines(k); // which lines each point is on (or an endpoint of)
vi which_ln(k, -1); // canonical line the point is on/endpoint of
for (auto &[x, y] : pol) cin >> x >> y;
for (auto &[x, y] : pts) cin >> x >> y;
copy(all(pol), begin(all_pts));
copy(all(pts), begin(all_pts) + n);
rep(i, 0, n) {
on_lines[i] = {i, (i - 1 + n) % n};
which_ln[i] = i;
P u = pol[i], v = pol[(i + 1) % n];
rep(j, 0, m) {
P p = pts[j];
if (u.cross(v, p) == 0 && (u - p).dot(v - p) <= 0) {
lin[i].push_back(n + j);
on_lines[n + j].insert(i);
// might be on multiple lines if it coincides with a vertex, so don't break out here
}
}
sort(all(lin[i]), [&](int a, int b) {
return (pts[a] - u).dist2() < (pts[b] - u).dist2();
});
}
rep(i, 0, m) which_ln[n + i] = *on_lines[n + i].begin();
rep(i, 0, n) rep(j, 0, m) {
// canonical line for a point that coincides with vertex
if (pol[i] == pts[j]) which_ln[n + j] = i;
}
// rep(i, 0, k) cout << "which_ln[" << i << "] = " << which_ln[i] << '\n';
// build the graph
vector<vector<pair<int, ld>>> adj(k);
auto do_thing = [&](int i, int j) -> void { // i comes before j in ccw order
// add an edge if the segment only intersects those that a or b are on
// (or endpoints of)
// we also we need to make sure the edge is inside the (simple) polygon
P a = all_pts[i], b = all_pts[j];
bool ok = true;
int left = which_ln[i], rght = which_ln[j];
if (left > rght) rght += n;
rep(btwn, left + 1, rght) {
if (sideOf(a, b, pol[btwn % n]) > 0) {
// cout << a << " -> " << b << " is on wrong side of " << pol[btwn % n] << '\n';
ok = false;
break;
}
}
if (!ok) return;
rep(l, 0, n) {
if (on_lines[i].count(l) || on_lines[j].count(l)) continue;
if (doSegInter(a, b, pol[l], pol[(l + 1) % n])) {
// cout << "intersection between " << a << ", " << b << " and " << pol[l] << ", " << pol[(l + 1) % n] << '\n';
ok = false;
break;
}
}
if (!ok) return;
ld d = (a - b).dist();
adj[i].emplace_back(j, d);
adj[j].emplace_back(i, d);
// cout << a << " <-> " << b << " = " << d << '\n';
};
rep(i, 0, n) {
rep(j, i + 1, n) {
do_thing(i, j);
for (int k : lin[j]) do_thing(i, k);
for (int k : lin[i]) do_thing(k, j);
for (int k : lin[i])
for (int l : lin[j]) do_thing(k, l);
}
}
// // print adj
// rep(i, 0, k) {
// cout << i << ": {\n";
// for (auto [j, d] : adj[i]) cout << "\t-> " << j << " = " << d << "\n";
// cout << "}\n";
// }
// compute all-pairs shortest paths
vector<vector<ld>> dist(k, vector<ld>(k, 1e18));
rep(i, 0, k) dist[i][i] = 0;
rep(i, 0, k) for (auto [j, d] : adj[i]) dist[i][j] = min(dist[i][j], d);
rep(h, 0, k) rep(i, 0, k) rep(j, 0, k)
dist[i][j] = min(
dist[i][j],
dist[i][h] + dist[h][j]);
// // print dist
// cout << "\ndist:\n";
// rep(i, 0, k) {
// cout << i << ": {\n";
// rep(j, 0, k) cout << "\t-> " << j << " = " << dist[i][j] << "\n";
// cout << "}\n";
// }
// to this end we first want an ordering of all the points in pts, based on the order in lines
vector<int> ord;
bitset<100> vis;
rep(l, 0, n) {
for (int ind : lin[l]) {
if (vis[ind]) continue;
vis[ind] = true;
ord.push_back(ind);
}
}
// print the path and the distance while computing
ld res = 0;
rep(i, 0, sz(ord)) {
int u = ord[i], v = ord[(i + 1) % sz(ord)];
res += dist[u][v];
// cout << all_pts[u] << " -> " << all_pts[v] << " = " << dist[u][v] << '\n';
}
cout << setprecision(10) << fixed << res << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.6568542495
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.6491106407
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.6568542495
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.6491106407
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 22ms
memory: 4040kb
input:
76 98 268 97 299 202 133 205 110 251 384 226 332 198 532 241 448 83 268 82 543 62 873 93 387 317 905 90 945 132 827 335 983 222 919 534 945 264 910 287 789 705 837 176 793 563 777 665 782 345 746 315 715 315 810 161 369 599 278 671 641 423 703 344 753 619 672 402 596 709 161 701 216 857 325 942 135 ...
output:
17780.5426687992
result:
wrong answer 1st numbers differ - expected: '14645.5751139', found: '17780.5426688', error = '0.2140556'