제출 #529966

#제출 시각아이디문제언어결과실행 시간메모리
529966fhvirusFences (JOI18_fences)C++17
100 / 100
16 ms676 KiB
// 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...