Submission #529058

#TimeUsernameProblemLanguageResultExecution timeMemory
529058wiwihoFences (JOI18_fences)C++14
0 / 100
1 ms316 KiB
#include<bits/stdc++.h> #define printv(a, b) { \ for(auto pv : a) b << pv << " "; \ b << "\n"; \ } #define eb emplace_back #define pob pop_back() #define iter(a) a.begin(), a.end() #define lsort(a) sort(iter(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define mp make_pair #define F first #define S second using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 1000000007; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; ld eps = 1e-6; ostream& operator<<(ostream& o, pdd p){ return o << '(' << p.F << ',' << p.S << ')'; } 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); } pdd operator*(ld a, pdd b){ return mp(a * b.F, a * b.S); } pdd operator-(pdd a){ return mp(-a.F, -a.S); } ld cross(pdd a, pdd b){ return a.F * b.S - a.S * b.F; } ld dot(pdd a, pdd b){ return a.F * b.F + a.S * b.S; } int ori(pdd a, pdd b){ ld tmp = cross(a, b); if(abs(tmp - 0) <= eps) return 0; else if(tmp > 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; } ld abs(pdd a){ return sqrt(a.F * a.F + a.S * a.S); } ld abs2(pdd a){ return a.F * a.F + a.S * a.S; } pdd proj(pdd p, pdd a, pdd b){ return cross(p - a, b - a) / abs2(b - a) * (b - a); } bool canproj(pdd p, pdd a, pdd b){ if(abs(a - b) < eps) return false; return dot(b - a, p - a) >= -eps && dot(a - b, p - b) >= -eps; } int n; int S; vector<pair<pdd, pdd>> seg; vector<pdd> now; vector<int> id; vector<bool> use; ld sum = 0; ld ans = 1e87; vector<pair<pdd, pdd>> border; bool check(pdd a, pdd b){ for(int i = 0; i + 1 < now.size(); i++){ if(intersect(now[i], now[i + 1], a, b)) return false; } for(auto i : border){ if(intersect(i.F, i.S, a, b)) return false; } return true; } bool inside(){ pdd v = mp(1, 48763); int cnt = 0; for(int i = 0; i < now.size(); i++){ int nxt = (i + 1) % now.size(); if(ori(v, now[i]) * ori(v, now[nxt]) < 0 && ori(now[nxt] - now[i], v - now[i]) * ori(now[nxt] - now[i], -now[i]) < 0) cnt++; } return cnt % 2; } pair<pdd, pdd> owo(int lstx, int nxtx){ auto lst = seg[lstx], nxt = seg[nxtx]; vector<pair<pdd, pdd>> tmp; tmp.eb(mp(lst.F, nxt.F)); tmp.eb(mp(lst.F, nxt.S)); tmp.eb(mp(lst.S, nxt.F)); tmp.eb(mp(lst.S, nxt.S)); auto tryproj = [&](pdd p, pdd a, pdd b, int t){ if(canproj(p, a, b)){ if(t == 0) tmp.eb(mp(p, proj(p, a, b))); else tmp.eb(mp(proj(p, a, b), p)); } }; tryproj(lst.F, nxt.F, nxt.S, 0); tryproj(lst.S, nxt.F, nxt.S, 0); tryproj(nxt.F, lst.F, lst.S, 1); tryproj(nxt.S, lst.F, lst.S, 1); sort(iter(tmp), [&](pair<pdd, pdd> a, pair<pdd, pdd> b){ return abs(a.F - a.S) > abs(b.F - b.S) + eps; }); for(auto i : tmp){ if(check(i.F, i.S)) return i; } return mp(mp(1e87, 1e87), mp(1e87, 1e87)); } void f(){ //cerr << "test "; //printv(now, cerr); if(id.size() >= 2){ auto tmp = owo(id.back(), id.front()); if(tmp.F.F == 1e87) goto qq; sum += abs(tmp.F - tmp.S); now.eb(tmp.F); now.eb(tmp.S); if(inside()) ans = min(ans, sum); now.pob; now.pob; sum -= abs(tmp.F - tmp.S); } qq:; for(int i = 0; i < n; i++){ if(use[i]) continue; if(id.empty()){ id.eb(i); use[i] = true; f(); use[i] = false; id.pob; continue; } auto tmp = owo(id.back(), i); if(tmp.F.F == 1e87) continue; now.eb(tmp.F); now.eb(tmp.S); sum += abs(tmp.F - tmp.S); id.eb(i); use[i] = true; f(); use[i] = false; id.pob; sum -= abs(tmp.F - tmp.S); now.pob; now.pob; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cerr.tie(0); cin >> n; cin >> S; seg.resize(n); for(int i = 0; i < n; i++){ cin >> seg[i].F.F >> seg[i].F.S >> seg[i].S.F >> seg[i].S.S; } seg.eb(mp(mp(S, S), mp(S, S))); seg.eb(mp(mp(S, -S), mp(S, -S))); seg.eb(mp(mp(-S, S), mp(-S, S))); seg.eb(mp(mp(-S, -S), mp(-S, -S))); n += 4; use.resize(n); border.eb(mp(mp(S, S), mp(S, -S))); border.eb(mp(mp(S, -S), mp(-S, -S))); border.eb(mp(mp(-S, -S), mp(-S, S))); border.eb(mp(mp(-S, S), mp(S, S))); border.eb(mp(mp(S, S), mp(-S, -S))); border.eb(mp(mp(S, -S), mp(-S, S))); f(); cout << fixed << setprecision(20) << ans << "\n"; return 0; }

Compilation message (stderr)

fences.cpp: In function 'bool check(pdd, pdd)':
fences.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i + 1 < now.size(); i++){
      |                    ~~~~~~^~~~~~~~~~~~
fences.cpp: In function 'bool inside()':
fences.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < now.size(); i++){
      |                    ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...