oj.uz

Submission #529061

# Submission time Handle Problem Language Result Execution time Memory
529061 2022-02-22T04:51:57 Z wiwiho Fences (JOI18_fences) C++14
18 / 100
 1000 ms 312 KB 
#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];
    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)){
            //cerr << "canproj " << p << " " << a << " " << b << " " << proj(p, a, b) << "\n";
            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(){

    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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 7 ms 204 KB Output is correct
22 Execution timed out 1085 ms 204 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 7 ms 204 KB Output is correct
22 Execution timed out 1085 ms 204 KB Time limit exceeded
23 Halted 0 ms 0 KB -