QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152252 | #5479. Traveling Salesperson in an Island | fhvirus | WA | 7ms | 3788kb | C++17 | 4.3kb | 2023-08-27 20:57:55 | 2023-08-27 20:57:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int) (x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef NONTOI
#define debug(args...) LKJ("\033[1;32m["#args"]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void print(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b], ++a; }
#else
#define debug(...) ((void)0)
#define print(...) ((void)0)
#endif
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0): x(x), y(y) {}
bool operator< (P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator== (P p) const { return tie(x, y) == tie(p.x, p.y); }
bool operator!= (P p) const { return tie(x, y) != tie(p.x, p.y); }
P operator + (P p) const { return P(x + p.x, y + p.y); }
P operator - (P p) const { return P(x - p.x, y - p.y); }
P operator * (T d) const { return P(x * d, y * d); }
P operator / (T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double)dist2()); }
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); }
P perp() const { return P(-y, x); }
P normal() const { return perp().unit(); }
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
friend ostream& operator<< (ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
template <class P> bool onSegment(P s, P e, P p)
{ return p.cross(s, e) == 0 and (s - p).dot(e - p) <= 0; }
template <class P> bool segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
if (sgn(oa) * sgn(ob) < 0 and sgn(oc) * sgn(od) < 0)
return true;
return false;
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin.exceptions(cin.failbit);
typedef Point<ll> P;
int n, m;
cin >> n >> m;
vector<P> ps(n), port(m);
for (auto &[x, y]: ps) cin >> x >> y;
for (auto &[x, y]: port) cin >> x >> y;
ps.push_back(ps[0]);
vi on_id(m);
rep (i, 0, m) rep (j, 0, n) {
if (onSegment(ps[j], ps[j+1], port[i])) {
on_id[i] = j;
break;
}
}
vi ord(m);
iota(all(ord), 0);
sort(all(ord), [&](int a, int b) {
if (on_id[a] != on_id[b]) return on_id[a] < on_id[b];
P c = ps[on_id[a]];
return (port[a] - c).dist2() < (port[b] - c).dist2();
});
auto ps2 = ps;
for (auto &p: ps2) p = p * 2;
auto inside = [&](P p) -> bool {
bool in = false;
P pp = p + P(10000, 1);
rep (i, 0, n)
in ^= segInter(p, pp, ps2[i], ps2[i+1]);
return in;
};
int N = n + m;
const double INF = 1e18;
vector<vector<double>> dis(N, vector<double>(N, INF));
rep (i, 0, N) dis[i][i] = 0;
rep (i, 0, n) dis[i][(i+1)%n] = dis[(i+1)%n][i] = (ps[i] - ps[i+1]).dist();
const auto can_build = [&](P a, P b) {
rep (i, 0, n) if (segInter(a, b, ps[i], ps[i+1]) or (ps[i] != a and ps[i] != b and onSegment(a, b, ps[i]))) return false;
if (!inside(a + b)) return false;
debug(a, b, (a - b).dist());
return true;
};
rep (i, 0, n) rep (j, i+1, n)
if (can_build(ps[i], ps[j])) dis[i][j] = dis[j][i] = (ps[i] - ps[j]).dist();
rep (i, 0, m) rep (j, i+1, m)
if (can_build(port[i], port[j])) dis[i+n][j+n] = dis[j+n][i+n] = (port[i] - port[j]).dist();
rep (i, 0, n) rep (j, 0, m)
if (can_build(ps[i], port[j])) dis[i][j+n] = dis[j+n][i] = (port[j] - ps[i]).dist();
rep (i, 0, m) {
int j = on_id[i];
dis[i+n][j] = dis[j][i+n] = (port[i] - ps[j]).dist();
j = (j + 1) % n;
dis[i+n][j] = dis[j][i+n] = (port[i] - ps[j]).dist();
}
rep (k, 0, N) rep (i, 0, N) rep (j, 0, N)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
ord.push_back(ord[0]);
double ans = 0;
rep (i, 0, m)
ans += dis[ord[i]+n][ord[i+1]+n];
cout << setprecision(12) << fixed;
cout << ans << '\n';
assert(ans < INF);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3676kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.656854249492
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
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.649110640674
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.656854249492
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3608kb
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.649110640674
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 7ms
memory: 3748kb
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:
16621.460126188678
result:
wrong answer 1st numbers differ - expected: '14645.5751139', found: '16621.4601262', error = '0.1349134'