QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387470#5104. Guardians of the Galleryucup-team1209#WA 1ms4092kbC++204.6kb2024-04-12 15:32:542024-04-12 15:32:54

Judging History

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

  • [2024-04-12 15:32:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4092kb
  • [2024-04-12 15:32:54]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int mod = 998244353;
const db eps = 1e-9;
const int N = 505;
using pr = std::pair<int, int>;
struct p2 {
	db x, y;
	db norm() const {
		return x * x + y * y;
	}
	db abs() const {
		return std::sqrt(norm());
	}
};
p2 r90(p2 x) {
	return {-x.y, x.x};
}
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}; }
p2 operator * (p2 x, db y) { return {x.x * y, x.y * y}; }
db operator * (p2 x, p2 y) {
	return x.x * y.y - x.y * y.x;
}
db operator % (p2 x, p2 y) {
	return x.x * y.x + x.y * y.y;
}
int half(p2 x) {
	return x.y < -eps || (std::fabs(x.y) < eps & x.x < eps); 
}
int cmp(p2 a, p2 b) {
	return half(a) == half(b) ? a * b > 0 : half(b);
}
int cmp_eq(p2 A, p2 B) {
	return half(A) == half(B) && fabs(A * B) < eps;
}
bool operator == (p2 x, p2 y) {
	return fabs(x.x - y.x) < eps && fabs(x.y - y.y) < eps;
}
bool operator != (p2 x, p2 y) {
	return fabs(x.x - y.x) > eps || fabs(x.y - y.y) > eps;
}


struct seg {
	p2 x, y;
	p2 f() {
		p2 r = r90(x - y);
		db rr = r.abs();
		r.x /= rr;
		r.y /= rr;
		return r;
	}
	p2 proj(p2 o) {
		db X = (x - o) * (y - o) / (x - y).abs();
		return o + f() * X;
	}
	db onseg(p2 o) {
		return (o - x) % (o - y) < eps;
	}
};

db sgn(db x) {
	return x < -eps ? -1 : x > eps;
}
int ccw(p2 a, p2 b, p2 c) {
	int sign = sgn((b - a) * (c - a));
	if(sign == 0) {
		if(sgn((b - a) % (c - a)) == -1) return 2;
		if((c - a).norm() > (b - a).norm() + eps) return -2;
	}
	return sign;
}
bool is_isc(const seg & x, const seg & y) {
	return ccw(x.x, y.y, y.x) * ccw(x.x, x.y, y.y) <= 0 &&
		ccw(y.x, y.y, x.x) * ccw(y.x, y.y, x.y) <= 0;
}

int n;
p2 a[N];
std::vector<p2> v;

p2 start, goal;

bool contains(seg x) {
	p2 t = x.y - x.x; db tr = t.abs();
	t.x /= tr, t.y /= tr;
	std::vector<std::pair<db, int>> V;
	for(int i = 0;i < n;++i) {
		p2 u = a[i], v = a[(i + 1) % n];
		u = u - x.x;
		v = v - x.x;
		int du = sgn(u * t), dv = sgn(v * t);
		if(du != dv) {
			p2 delta = v - u;
			db inc = (u * t) / (delta * t);
			V.emplace_back((u - delta * inc) % t, du - dv);
		}
	}
	db L = 0, R = (x.y - x.x) % t;
	V.emplace_back(-1e5, 0);
	V.emplace_back(1e5, 0);
	sort(V.begin(), V.end());
	int sum = 0;
	for(int i = 0;i + 1 < (int) V.size();++i) {
		sum += V[i].second;
		if(sum == 0) {
			db l = V[i].first, r = V[i + 1].first;
			db len = std::min(r, R) - std::max(l, L);
			if(len > eps) return 0;
		}
	}
	return 1;
}
db e[N][N];
int main() {
#ifdef zqj
	freopen("$.in", "r", stdin);
#endif 
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;++i) {
		cin >> a[i].x >> a[i].y;
	}
	cin >> start.x >> start.y;
	cin >> goal.x >> goal.y;
	start = start - goal;
	for(int i = 0;i < n;++i) {
		a[i] = a[i] - goal;
	}
	goal = {0, 0};
	std::vector<p2> v(a, a + n);
	std::vector<seg> segs;
	for(int i = 0;i < n;++i) {
		segs.push_back({a[i], a[(i + 1) % n]});
	}
	sort(v.begin(), v.end(), cmp);
	auto vv = v;
	vv.erase(unique(vv.begin(), vv.end(), cmp_eq), vv.end());
	p2 F = {1e5, 1e5};
	std::vector<p2> l(vv.size(), F), r(l);
	for(auto [x, y] : segs) {
		if(x * y < 0) std::swap(x, y);
		if(sgn(x * y) == 0) {
			continue;
		}
		int L = lower_bound(vv.begin(), vv.end(), x, cmp) - vv.begin();
		int R = lower_bound(vv.begin(), vv.end(), y, cmp) - vv.begin();
		if(x.norm() < r[L].norm()) {
			r[L] = x;
		}
		if(y.norm() < l[R].norm()) {
			l[R] = y;
		}
	}
	std::vector<p2> p;
	for(int i = 0;i < (int) vv.size();++i) {
		if(l[i] != F && contains({goal, l[i]})) p.push_back(l[i]);
		if(r[i] != F && r[i] != F && contains({goal, r[i]})) p.push_back(r[i]);
	}
	auto A = v;
	A.insert(A.end(), p.begin(), p.end());
	A.push_back(start);
	A.push_back(goal);
	int N = A.size();
	for(int i = 0;i < N;++i) {
		for(int j = 0;j < N;++j) {
			if(contains({A[i], A[j]})) {
				e[i][j] = (A[i] - A[j]).abs();
			} else {
				e[i][j] = 1e18;
			}
		}
	}
	for(int i = 0;i < N;++i) {
		for(int j = 0;j < N;++j) {
			for(int k = 0;k < N;++k) {
				e[j][k] = std::min(e[j][k], e[j][i] + e[i][k]);
			}
		}
	}
	int st = find(A.begin(), A.end(), start) - A.begin();
	db ans = 1e18;
	for(int i = 0;i < N;++i) {
		for(int j = 0;j < (int) p.size();++j) {
			seg S {p[j], p[(j + 1) % p.size()]};
			p2 p = S.proj(A[i]);
			if(S.onseg(p)) {
				if(contains({A[i], p})) {
					ans = std::min(ans, e[st][i] + (A[i] - p).abs());
				}
			}
		}
	}
	printf("%.20lf\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4092kb

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:

43.41983504804584725889

result:

wrong answer 1st numbers differ - expected: '29.0000000', found: '43.4198350', error = '0.4972357'