QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103191#5479. Traveling Salesperson in an Island8BQubeWA 4ms3600kbC++174.7kb2023-05-04 18:25:382023-05-04 18:25:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-04 18:25:39]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3600kb
  • [2023-05-04 18:25:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

const double INF = 9e18;
typedef pair<double, double> pdd;

pll operator-(const pll &a, const pll &b) { return pll(a.X - b.X, a.Y - b.Y); }
pll operator+(const pll &a, const pll &b) { return pll(a.X + b.X, a.Y + b.Y); }
pll operator*(const pll &a, const ll &b) { return pll(a.X * b, a.Y * b); }
pdd operator/(const pll &a, const double &b) { return pdd(a.X * b, a.Y * b); }
ll dot(const pll &a, const pll &b) { return a.X * b.X + a.Y * b.Y; }
double dot(const pdd &a, const pdd &b) { return a.X * b.X + a.Y * b.Y; }
double abs(const pll &a) { return sqrt(dot(a, a)); }
ll abs2(const pll &a) { return sqrt(dot(a, a)); }
double abs(const pdd &a) { return sqrt(dot(a, a)); }
int sign(const ll &a) { return a == 0 ? 0 : a > 0 ? 1 : -1; }
ll cross(const pll &a, const pll &b) { return a.X * b.Y - a.Y * b.X; }
int ori(const pll &a, const pll &b, const pll &c) { return sign(cross(b - a, c - a)); }

bool collin(const pll &p1, const pll &p2, const pll &p3) {
    return sign(cross(p1 - p3, p2 - p3)) == 0;
}

bool btw(const pll &p1, const pll &p2, const pll &p3) {
    if (!collin(p1, p2, p3)) return 0;
    return sign(dot(p1 - p3, p2 - p3)) <= 0;
}

bool seg_intersect(const pll &p1, const pll &p2, const pll &p3, const pll &p4) {
    int a123 = ori(p1, p2, p3);   
    int a124 = ori(p1, p2, p4);   
    int a341 = ori(p3, p4, p1);   
    int a342 = ori(p3, p4, p2);
    if (a123 == 0 && a124 == 0) return 0;
    return a123 * a124 < 0 && a341 * a342 < 0;
}

pdd intersect(const pll &p1, const pll &p2, const pll &p3, const pll &p4) {
    ll a123 = cross(p2 - p1, p3 - p1);
    ll a124 = cross(p2 - p1, p4 - p1);
    return (p4 * a123 - p3 * a124) / (a123 - a124);
}

pll arr[105], given[105];
int pos[105], idx[105];
double dp[205][205];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> arr[i].X >> arr[i].Y;
    for (int i = 0; i < m; ++i)
        cin >> given[i].X >> given[i].Y;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (btw(arr[j], arr[(j + 1) % n], given[i])) {
                pos[i] = j;
                break;
            }
    iota(idx, idx + m, 0);
    sort(idx, idx + m, [&](int a, int b) {
        if (pos[a] != pos[b]) return pos[a] < pos[b];
        return abs2(given[a] - arr[pos[a]]) < abs2(given[b] - arr[pos[b]]); 
    });

    auto inpoly = [&](int p, pll s, pll t) {
        cerr << p << " (" << s.X << ", " << s.Y << ") (" << t.X << ", " << t.Y << ")\n"; 
        for (int i = 0; i < n; ++i)
            if (seg_intersect(s, t, arr[i], arr[(i + 1) % n])) {
                cerr << "intersect " << i << "\n";
                return false;
            }
        vector<pll> dots(1, s);
        vector<int> pp(1, p), id;
        for (int i = 0; i < n; ++i)
            if (btw(s, t, arr[i]))
                dots.pb(arr[i]), pp.pb(i);
        id.resize(SZ(dots), 0);
        iota(ALL(id), 0);
        sort(ALL(id), [&](int a, int b) {
            return abs2(dots[a] - s) < abs2(dots[b] - s);
        });
        id.pb(SZ(dots)), dots.pb(t);
        for (int i = 0; i + 1 < SZ(dots); ++i) {
            int cur = pp[id[i]];
            pll u = dots[id[i]], v = dots[id[i + 1]];
            cerr << "judge " << cur << "(" << u.X << ", " << u.Y << ") (" << v.X << ", " << v.Y << ")\n"; 
            if (ori(u, arr[(cur + 1) % n], v) < 0 || ori(u, arr[(cur + n - 1) % n], v) > 0) return false;
        }
        cerr << p << " (" << s.X << ", " << s.Y << ") (" << t.X << ", " << t.Y << ") succ\n"; 
        return true;
    };

    for (int i = 0; i < n + m; ++i)
        for (int j = 0; j < n + m; ++j)
            dp[i][j] = INF;
    for (int i = 0; i < n + m; ++i)
        for (int j = i; j < n + m; ++j) {
            if (i == j) dp[i][j] = 0;
            else {
                int p;
                pll u, v;
                if (i < n) u = arr[i], p = i;
                else u = given[i - n], p = pos[i - n];
                if (j < n) v = arr[j];
                else v = given[j - n];
                if (inpoly(p, u, v))
                    dp[i][j] = dp[j][i] = abs(u - v);
            }
        }
    for (int k = 0; k < n + m; ++k)
        for (int i = 0; i < n + m; ++i)
            for (int j = 0; j < n + m; ++j)
                dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]);

    auto query = [&](int a, int b) {
        return dp[a + n][b + n]; 
    };

    double ans = 0;
    for (int i = 0; i < m; ++i)
        ans += query(idx[i], idx[(i + 1) % m]);
    
    cout << fixed << setprecision(20) << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 3600kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
1 2
2 1
0 1

output:

6.82842712474618984686

result:

wrong answer 1st numbers differ - expected: '5.6568542', found: '6.8284271', error = '0.2071068'