QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105794#5479. Traveling Salesperson in an Island8BQubeWA 6ms3928kbC++204.5kb2023-05-15 14:41:342023-05-15 14:41:37

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-15 14:41:37]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3928kb
  • [2023-05-15 14:41:34]
  • 提交

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);
}

// ori(a, b, c) > 0
bool btwangle(const pll &a, const pll &b, const pll &c, const pll &p, int strict) {
    return ori(a, b, p) >= strict && ori(a, p, c) >= strict;
}

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 = [&](pll s, pll t) {
        for (int i = 0; i < n; ++i)
            if (seg_intersect(s, t, arr[i], arr[(i + 1) % n]))
                return false;
        for (int i = 0; i < n; ++i)
            if (btw(s, t, arr[i])) {
                pll prv = arr[(i + n - 1) % n], nxt = arr[(i + 1) % n];
                if (ori(arr[i], nxt, prv) > 0) {
                    if (!btwangle(arr[i], nxt, prv, s, 0)) return false;
                    if (!btwangle(arr[i], nxt, prv, t, 0)) return false;
                }
                else {
                    if (btwangle(arr[i], prv, nxt, s, 1)) return false;
                    if (btwangle(arr[i], prv, nxt, t, 1)) return false;
                }
            }
        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 {
                pll u, v;
                if (i < n) u = arr[i];
                else u = given[i - n];
                if (j < n) v = arr[j];
                else v = given[j - n];
                if (inpoly(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: 100
Accepted
time: 2ms
memory: 3592kb

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: 0
Accepted
time: 2ms
memory: 3656kb

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.64911064067351986751

result:

ok found '16.6491106', expected '16.6491106', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

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

output:

5.65685424949238058190

result:

ok found '5.6568542', expected '5.6568542', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

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.64911064067351986751

result:

ok found '16.6491106', expected '16.6491106', error '0.0000000'

Test #5:

score: -100
Wrong Answer
time: 6ms
memory: 3928kb

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:

13621.60138424071919871494

result:

wrong answer 1st numbers differ - expected: '14645.5751139', found: '13621.6013842', error = '0.0699169'