QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103191 | #5479. Traveling Salesperson in an Island | 8BQube | WA | 4ms | 3600kb | C++17 | 4.7kb | 2023-05-04 18:25:38 | 2023-05-04 18:25:39 |
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);
}
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'