Submission #532558

#TimeUsernameProblemLanguageResultExecution timeMemory
532558wiwihoFences (JOI18_fences)C++14
51 / 100
406 ms262148 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } using pdd = pair<ld, ld>; ld eps = 1e-9; pdd operator+(pdd a, pdd b){ return mp(a.F + b.F, a.S + b.S); } pdd operator-(pdd a, pdd b){ return mp(a.F - b.F, a.S - b.S); } ld dot(pdd a, pdd b){ return a.F * b.F + a.S * b.S; } ld cross(pdd a, pdd b){ return a.F * b.S - a.S * b.F; } ld abs2(pdd a){ return a.F * a.F + a.S * a.S; } ld abs(pdd a){ return sqrt(abs2(a)); } pdd operator*(ld i, pdd p){ return mp(i * p.F, i * p.S); } int ori(pdd a, pdd b){ if(abs(cross(a, b)) <= eps) return 0; else if(cross(a, b) > 0) return 1; else return -1; } bool intersect(pdd a, pdd b, pdd c, pdd d){ return ori(b - a, c - a) * ori(b - a, d - a) < 0 && ori(d - c, a - c) * ori(d - c, b - c) < 0; } bool canproj(pdd p, pdd a, pdd b){ return dot(b - a, p - a) >= 0 && dot(a - b, p - b) >= 0; } pdd getproj(pdd p, pdd a, pdd b){ if(abs2(a - b) <= eps) return a; return a + dot(p - a, b - a) / abs2(b - a) * (b - a); } pdd v1 = mp(0, 0), v2 = mp(48763, 3234234); struct Line{ pdd a, b; }; struct edge{ int to; ld w; int f; }; ostream& operator<<(ostream& o, edge e){ return o << '(' << e.to << ',' << e.w << ',' << e.f << ')'; } int n; ld S; vector<Line> border; vector<Line> e; vector<pdd> pos; vector<vector<int>> ps; vector<vector<edge>> g; map<pdd, int> vid; int ts; void init(){ cin >> n >> S; e.resize(n); for(int i = 0; i < n; i++){ cin >> e[i].a.F >> e[i].a.S >> e[i].b.F >> e[i].b.S; } border.eb(Line({mp(S, S), mp(S, -S)})); border.eb(Line({mp(-S, -S), mp(S, -S)})); border.eb(Line({mp(-S, -S), mp(-S, S)})); border.eb(Line({mp(S, S), mp(-S, S)})); border.eb(Line({mp(S, -S), mp(-S, S)})); border.eb(Line({mp(-S, -S), mp(S, S)})); e.eb(Line({mp(S, S), mp(S, S)})); e.eb(Line({mp(S, -S), mp(S, -S)})); e.eb(Line({mp(-S, S), mp(-S, S)})); e.eb(Line({mp(-S, -S), mp(-S, -S)})); n += 4; ps.resize(n); } bool check(pdd a, pdd b){ for(auto i : border){ if(intersect(a, b, i.a, i.b)) return false; } return true; } int getv(pdd p){ if(vid.find(p) != vid.end()) return vid[p]; vid[p] = ts++; pos.eb(p); g.eb(); return vid[p]; } bool foxyy(pdd a, pdd b){ return intersect(a, b, v1, v2); } void addedge(int x, pdd a, int y, pdd b){ if(!check(a, b)){ //cerr << "qq " << a << " " << b << "\n"; return; } int av = getv(a); int bv = getv(b); //cerr << "addedge " << x << " " << av << " " << y << " " << bv << "\n"; ps[x].eb(av); ps[y].eb(bv); g[av].eb(edge({bv, abs(a - b), foxyy(a, b)})); g[bv].eb(edge({av, abs(a - b), foxyy(a, b)})); //cerr << "addedge " << a << " " << b << " " << abs(a - b) << " " << foxyy(a, b) << "\n"; } void tryproj(int x, pdd p, int y, pdd a, pdd b){ if(!canproj(p, a, b)) return; //cerr << "canproj " << x << " " << p << " " << y << " " << getproj(p, a, b) << "\n"; addedge(x, p, y, getproj(p, a, b)); } void buildedges(int x, int y){ addedge(x, e[x].a, y, e[y].a); addedge(x, e[x].b, y, e[y].a); addedge(x, e[x].a, y, e[y].b); addedge(x, e[x].b, y, e[y].b); tryproj(x, e[x].a, y, e[y].a, e[y].b); tryproj(x, e[x].b, y, e[y].a, e[y].b); tryproj(y, e[y].a, x, e[x].a, e[x].b); tryproj(y, e[y].b, x, e[x].a, e[x].b); } void buildline(int id){ for(int i : ps[id]){ for(int j : ps[id]){ g[i].eb(edge({j, 0, foxyy(pos[i], pos[j])})); } } } struct info{ ld d; int v; int f; bool operator<(info b) const{ return d > b.d; } }; ld calc(int s){ std::priority_queue<info> pq; vector<vector<ld>> dis(2, vector<ld>(ts, 1e20)); dis[0][s] = 0; pq.push(info({0, s, 0})); while(!pq.empty()){ ld d = pq.top().d; int v = pq.top().v, f = pq.top().f; pq.pop(); if(abs(d - dis[f][v]) > eps) continue; for(auto i : g[v]){ int nf = f ^ i.f; if(d + i.w >= dis[nf][i.to] - eps) continue; dis[nf][i.to] = d + i.w; pq.push(info({d + i.w, i.to, nf})); } } //cerr << "calc " << s << " " << dis[1][s] << "\n"; return dis[1][s]; } void waassert(bool b){ if(b) return; cout << "WA\n"; exit(0); } int main(){ StarBurstStream init(); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++) buildedges(i, j); } for(int i = 0; i < n; i++) buildline(i); /*cerr << "graph\n"; for(int i = 0; i < ts; i++){ cerr << i << " " << pos[i] << " "; printv(g[i], cerr); }*/ waassert(ts <= 4e5); ld ans = 1e20; for(int i = 0; i < ts; i++){ ans = min(ans, calc(i)); } cout << fixed << setprecision(20) << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...