제출 #529966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529966		fhvirus	Fences (JOI18_fences)	C++17	100 / 100	16 ms	676 KiB

fences

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

const double INF = 1e18;
const double eps = 1e-9;
int sign(double d) { return (d >= eps) - (d <= eps); }

struct Vec {
	double x, y;
	Vec () = default;
	Vec (const double& _x, const double& _y): x(_x), y(_y) {}
	const Vec operator + (const Vec& o) const { return Vec(x + o.x, y + o.y); }
	const Vec operator - (const Vec& o) const { return Vec(x - o.x, y - o.y); }
	const Vec operator * (const double& v) const { return Vec(x * v, y * v); }
	const double operator * (const Vec& o) const { return x * o.x + y * o.y; }
	const double operator ^ (const Vec& o) const { return x * o.y - y * o.x; }
	const double abs2 () const { return x * x + y * y; }
	const double abs () const { return sqrt(x * x + y * y); }
};
struct Seg {
	Vec a, b;
	Seg () = default;
	Seg (const Vec& _a, const Vec& _b): a(_a), b(_b) {}
	Seg (const int& _a, const int& _b, const int& _c, const int& _d)
		: a(_a, _b), b(_c, _d) {}
};
const int ori(const Vec& o, const Vec& a, const Vec& b)
{ return sign((a - o) ^ (b - o)); }
const bool intersect(const Seg& a, const Seg& b) {
	return ori(a.a, a.b, b.a) * ori(a.a, a.b, b.b) < 0
		and ori(b.a, b.b, a.a) * ori(b.a, b.b, a.b) < 0;
}
const bool has_T(const Vec& v, const Seg& s) {
	return sign((v - s.a) * (s.b - s.a)) > 0
		and sign((v - s.b) * (s.a - s.b)) > 0;
}
const Vec T_point(const Vec& v, const Seg& s) {
	const Vec AB = s.b - s.a;
	const Vec AV = v - s.a;
	return s.a + AB * ((AB * AV) / AB.abs2());
}

Seg diaA, diaB, uwu;
double dis[2];
void add_edge(const Vec& a, const Vec& b, const Vec& c, const Vec& d) {
	Seg ab(a, b), bc(b, c), cd(c, d);
	if (intersect(bc, diaA) or intersect(bc, diaB))
		return;
	bool owo = intersect(ab, uwu) xor intersect(bc, uwu) xor intersect(cd, uwu);
	dis[owo] = min(dis[owo], (c - b).abs());
}
void solve(const Seg& a, const Seg& b) {
	dis[0] = dis[1] = INF;
	add_edge(a.a, a.a, b.b, b.a);
	add_edge(a.a, a.b, b.b, b.a);
	add_edge(a.a, a.a, b.a, b.a);
	add_edge(a.a, a.b, b.a, b.a);
	if (has_T(a.a, b)) add_edge(a.a, a.a, T_point(a.a, b), b.a);
	if (has_T(a.b, b)) add_edge(a.a, a.b, T_point(a.b, b), b.a);
	if (has_T(b.a, a)) add_edge(a.a, T_point(b.a, a), b.a, b.a);
	if (has_T(b.b, a)) add_edge(a.a, T_point(b.b, a), b.b, b.a);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, S; cin >> N >> S;
	vector<Seg> segs;
	for (int A, B, C, D, i = 0; i < N; ++i) {
		cin >> A >> B >> C >> D;
		segs.emplace_back(A, B, C, D);
	}

	N = N + 4;
	for (const int& x: {S, -S})
		for (const int& y: {S, -S})
			segs.emplace_back(x, y, x, y);
	diaA = Seg(S, S, -S, -S);
	diaB = Seg(S, -S, -S, S);
	uwu = Seg(0, 0, 1, 3000);

	vector<vector<double>> dp(N * 2, vector<double>(N * 2, INF));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) {
			solve(segs[i], segs[j]);
			dp[i * 2][j * 2] = dp[i * 2 + 1][j * 2 + 1] = dis[0];
			dp[i * 2 + 1][j * 2] = dp[i * 2][j * 2 + 1] = dis[1];
		}

	for (int k = 0; k < N * 2; ++k)
		for (int i = 0; i < N * 2; ++i) if (dp[i][k] != INF)
			for (int j = 0; j < N * 2; ++j) if (dp[k][j] != INF)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

	double ans = INF;
	for (int i = 0; i < N; ++i)
		ans = min(ans, dp[i * 2][i * 2 + 1]);
	
	cout << setprecision(9) << fixed << ans << '\n';

	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49