QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152250 | #5479. Traveling Salesperson in an Island | fhvirus | RE | 0ms | 3784kb | C++17 | 4.3kb | 2023-08-27 20:56:58 | 2023-08-27 20:57:00 |
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[i][j+n] = (port[i] - ps[j]).dist();
j = (j + 1) % n;
dis[i+n][j] = dis[i][j+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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
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: -100
Dangerous Syscalls
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4