QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152250#5479. Traveling Salesperson in an IslandfhvirusRE 0ms3784kbC++174.3kb2023-08-27 20:56:582023-08-27 20:57:00

Judging History

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

  • [2023-08-27 20:57:00]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3784kb
  • [2023-08-27 20:56:58]
  • 提交

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

output:


result: