Submission #529063

#	Time	Username	Problem	Language	Result	Execution time	Memory
529063		wiwiho	Fences (JOI18_fences)	C++14	18 / 100	1083 ms	320 KiB

fences

#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 a + dot(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];
    pair<ld, pair<pdd, pdd>> mn = mp(1e87, mp(mp(1e87, 1e87), mp(1e87, 1e87)));
    
    auto tryseg = [&](pdd a, pdd b){
        if(check(a, b)) mn = min(mn, mp(abs2(a - b), mp(a, b)));
    };

    tryseg(lst.F, nxt.F);
    tryseg(lst.F, nxt.S);
    tryseg(lst.S, nxt.F);
    tryseg(lst.S, nxt.S);

    auto tryproj = [&](pdd p, pdd a, pdd b, int t){
        if(canproj(p, a, b)){
            //cerr << "canproj " << p << " " << a << " " << b << " " << proj(p, a, b) << "\n";
            if(t == 0) tryseg(p, proj(p, a, b));
            else tryseg(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);
    
    return mn.S;
}

void f(){

    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()){
            //cerr << "test " << sum << " ";
            //printv(now, cerr);
            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++){
      |                    ~~^~~~~~~~~~~~

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