QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95647#5479. Traveling Salesperson in an IslandBbakaWA 14ms4056kbC++145.6kb2023-04-11 08:16:202023-04-11 08:16:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-11 08:16:23]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:4056kb
  • [2023-04-11 08:16:20]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define FOR(i, begin, end, delta) for (int i = begin; i <= end; i += delta)
#define For(i, x) for (auto i : x)
#define fastios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl '\n'
#define rd(x) scanf("%lld", &x)
#define wc(x) putchar(x)
#define ws(x) printf("%s", x)
#define el puts("")
#define udm unordered_map<int, int>
#define inf 0x3f3f3f3f
#define set_inf(a) memset(&a, 0x3f, sizeof(a))
#define set_0(a) memset(&a, 0, sizeof(a))
#define set_unint(a) memset(&a, -1, sizeof(a))
using namespace std;
// define_var
const int M = 2e5 + 9;
// define_var
// function_begin
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}
void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
// function_end
// solve_begin
const double eps = 1e-9;
inline int sgn(double x) {
    if (fabs(x) <= eps)
        return 0;
    else if (x > 0)
        return 1;
    else
        return -1;
}
const int N = 320;
int n, m;
class Point {
public:
    double x, y;

    int id;

    Point(double _x = 0, double _y = 0) {
        x = _x;
        y = _y;
    }

    inline void init() {
        cin >> x >> y;
    }
    bool operator==(Point b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }

    Point operator-(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }

    Point operator+(const Point &b) const {
        return Point(x + b.x, y + b.y);
    }

    double operator^(const Point &b) const {
        return x * b.y - y * b.x;
    }

    double operator*(const Point &b) const {
        return x * b.x + y * b.y;
    }

    inline double dis(Point b) {
        return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y));
    }

    inline double len() {
        return sqrt(x * x + y * y);
    }
};
typedef Point Vector;
Point _Node[N];
int _cnt;
int tot = 0;
inline double segmentdist(Point st, Point ed, Point p) {
    Vector v1 = ed - st;
    Vector v2 = p - st;
    Vector v3 = p - ed;
    if (sgn(v1 * v2) < 0)
        return v2.len();
    else if (sgn(v1 * v3) > 0)
        return v3.len();
    else
        return fabs(v1 ^ v2) / v1.len();
}
inline bool onsegment(Point s, Point t, Point a) {
    return sgn((t - s) ^ (a - s)) == 0 && sgn((t - s) * (a - s)) > 0 && sgn((s - t) * (a - t)) > 0;
}
inline int Inter(Point a) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int u = i;
        int v = i % n + 1;
        if ((onsegment(_Node[u], _Node[v], a)) || _Node[u] == a)
            return 1; // 在多边形上
        double k = (_Node[v] - _Node[u]) ^ (a - _Node[u]);

        if (k > 0 && _Node[u].y < a.y && a.y <= _Node[v].y)
            cnt ^= 1;
        if (k < 0 && _Node[u].y >= a.y && a.y > _Node[v].y)
            cnt ^= 1;
    }
    if (cnt)
        return 1;
    else
        return 0;
}

inline bool check(int a, int b) {
    for (int i = 1; i <= n; ++i) {
        int u = i;
        int v = i % n + 1;
        double c1 = (_Node[a] - _Node[u]) ^ (_Node[v] - _Node[u]);
        double c2 = (_Node[b] - _Node[u]) ^ (_Node[v] - _Node[u]);
        double c3 = (_Node[u] - _Node[a]) ^ (_Node[b] - _Node[a]);
        double c4 = (_Node[v] - _Node[a]) ^ (_Node[b] - _Node[a]);
        if ((sgn(c1) * sgn(c2) < 0) && (sgn(c3) * sgn(c4) < 0))
            return false;
        if (onsegment(_Node[a], _Node[b], _Node[i]))
            return false;
    }

    Point _mid = _Node[a] + _Node[b];
    _mid.x /= 2.0;
    _mid.y /= 2.0;
    if (Inter(_mid))
        return true;
    else
        return false;
}

double dis[N][N];
Point Origin;
int Now_id;
inline bool cmp(int a, int b) {
    return dis[a][Now_id] < dis[b][Now_id];
}
vector<int> dot[N];
vector<int> _P;
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        _Node[++tot].init();
    }
    for (int i = 1; i <= m; ++i) {
        _Node[++tot].init();
        for (int j = 1; j <= n; ++j) {
            int u = j;
            int v = j % n + 1;
            if (onsegment(_Node[u], _Node[v], _Node[tot]) || _Node[u] == _Node[tot]) {
                dot[j].push_back(tot);
            }
        }
    }
    for (int i = 1; i <= tot; ++i)
        for (int j = 1; j <= tot; ++j) {
            if (i == j)
                dis[i][j] = 0;
            else
                dis[i][j] = 1e9;
        }

    for (int i = 1; i <= tot; ++i) {
        for (int j = i + 1; j <= tot; ++j) {
            if (_Node[i] == _Node[j])
                continue;
            if (!check(i, j))
                continue;
            dis[j][i] = dis[i][j] = fmin(dis[i][j], _Node[i].dis(_Node[j]));
        }
    }

    for (int k = 1; k <= tot; ++k) {
        for (int i = 1; i <= tot; ++i) {
            for (int j = 1; j <= tot; ++j) {
                dis[i][j] = fmin(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    int _m = 0;
    for (int i = 1; i <= n; ++i) {
        Now_id = i;
        sort(dot[i].begin(), dot[i].end(), cmp);
        for (auto v : dot[i]) {
            ++_m;
            _P.push_back(v);
        }
    }

    double mindis = 0;

    for (int i = 0; i < _m; ++i) {
        mindis += dis[_P[i]][_P[(i + 1) % _m]];
    }

    printf("%.15f\n", mindis);
    return;
}
signed main() {
    fastios int T = 1;
    while (T--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3748kb

input:

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

output:

5.656854249492381

result:

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

Test #2:

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

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

result:

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

Test #3:

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

input:

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

output:

5.656854249492381

result:

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

Test #4:

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

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

result:

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

Test #5:

score: -100
Wrong Answer
time: 14ms
memory: 4056kb

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:

15352.599056763636327

result:

wrong answer 1st numbers differ - expected: '14645.5751139', found: '15352.5990568', error = '0.0482756'