QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485713#5479. Traveling Salesperson in an IslandenwaskWA 22ms4040kbC++176.4kb2024-07-21 02:21:382024-07-21 02:21:38

Judging History

你现在查看的是最新测评结果

  • [2024-07-21 02:21:38]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:4040kb
  • [2024-07-21 02:21:38]
  • 提交

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'