QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105794 | #5479. Traveling Salesperson in an Island | 8BQube | WA | 6ms | 3928kb | C++20 | 4.5kb | 2023-05-15 14:41:34 | 2023-05-15 14:41:37 |
Judging History
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'