QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152252#5479. Traveling Salesperson in an IslandfhvirusWA 7ms3788kbC++174.3kb2023-08-27 20:57:552023-08-27 20:57:56

Judging History

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

  • [2023-08-27 20:57:56]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3788kb
  • [2023-08-27 20:57:55]
  • 提交

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'