QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387584#5479. Traveling Salesperson in an Islanducup-team1209RE 0ms4016kbC++202.6kb2024-04-12 17:03:362024-04-12 17:03:36

Judging History

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

  • [2024-04-12 17:03:36]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4016kb
  • [2024-04-12 17:03:36]
  • 提交

answer

#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 205;
struct p2 {
	int x, y;
	db abs() const {
		return std::sqrt(norm());
	}
	ll norm() const {
		return (ll) x * x + (ll) y * y;
	}
};
p2 operator + (p2 x, p2 y) { return {x.x + y.x, x.y + y.y}; }
p2 operator - (p2 x, p2 y) { return {x.x - y.x, x.y - y.y}; }
ll operator * (p2 x, p2 y) { return (ll) x.x * y.y - (ll) x.y * y.x; }
ll operator % (p2 x, p2 y) { return (ll) x.x * y.x + (ll) x.y * y.y; }
int sgn(ll x) {
	return x < 0 ? -1 : x > 0;
}
const db inf = 1e8;
const db eps = 1e-8;
bool contains(p2 x, p2 y, const std::vector<p2> & a) {
	using pr = std::pair<double, int>;
	std::vector<pr> e = {pr(-inf, 0), pr(inf, 0)};
	p2 t = y - x;
	auto f = [&](p2 a, p2 b, p2 c, p2 d) {
		return (b - a).abs() * ((c - a) * (d - c)) / ((b - a) * (d - c));
	};
	for(int i = 0;i < (int) a.size();++i) {
		p2 u = a[i], v = a[(i + 1) % a.size()];
		int a = sgn(t * (u - x));
		int b = sgn(t * (v - x));
		if(a != b) e.emplace_back(f(x, y, u, v), b - a);
	}
	sort(e.begin(), e.end());
	int sum = 0;
	db R = t.abs();
	for(int i = 0;i + 1 < (int) e.size();++i) {
		sum += e[i].second;
		if(sum == 0) {
			if(std::max<db>(e[i].first, 0) + eps < std::min<db>(e[i + 1].first, R)) {
				return 0;
			}
		}
	}
	return 1;
}
p2 a[N];

int n, m;
db d[N][N];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for(int i = 0;i < n + m;++i) {
		cin >> a[i].x >> a[i].y;
	}
	std::vector<int> idx(m);
	std::vector<db> dist(m);
	for(int i = 0;i < m;++i) {
		p2 z = a[i + n];
		for(int j = 0;j < n;++j) {
			p2 A = a[j], B = a[(j + 1) % n];
			if((z - A) * (z - B) == 0 && (z - A) % (z - B) <= 0) {
				idx[i] = j;
				dist[j] = (z - A).abs();
			}
		}
	}
	std::vector<int> rk(m);
	for(int i = 0;i < m;++i) {
		rk[i] = i;
	}
	sort(rk.begin(), rk.end(), [&](int x, int y) {
		if(idx[x] != idx[y]) {
			return idx[x] < idx[y];
		}
		return dist[x] < dist[y];
	});
	std::vector<p2> P(a, a + n);
	for(int i = 0;i < n + m;++i) {
		for(int j = 0;j < n + m;++j) {
			if(contains(a[i], a[j], P)) {
				d[i][j] = (a[i] - a[j]).abs();
			} else {
				d[i][j] = 1e18;
			}
		}
	}
	for(int i = 0;i < n + m;++i) {
		for(int j = 0;j < n + m;++j) {
			for(int k = 0;k < n + m;++k) {
				d[j][k] = std::min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
	db ans = 0;
	for(int i = 0;i < m;++i) {
		ans += d[n + rk[i]][n + rk[(i + 1) % m]];
	}
	printf("%.20lf\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4016kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
1 2
2 1
0 1

output:

5.65685424949238058190

result:

ok found '5.6568542', expected '5.6568542', error '0.0000000'

Test #2:

score: -100
Runtime Error

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: