oj.uz

Submission #584978

# Submission time Handle Problem Language Result Execution time Memory
584978 2022-06-28T08:02:38 Z 박상훈(#8379) Fences (JOI18_fences) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int A[111], B[111], C[111], D[111], n, S;

double dist(pair<int, int> p, pair<int, int> q){
    return sqrt((p.first-q.first)*(p.first-q.first) + (p.second-q.second)*(p.second-q.second));
}

int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    int x1 = b.first - a.first, x2 = c.first - a.first;
    int y1 = b.second - a.second, y2 = c.second - a.second;
    int ret = x1*y2-x2*y1;
    if (ret>0) return 1;
    if (ret<0) return -1;
    return 0;
}

bool cmp(pair<int, int> p, pair<int, int> q){
    if (ccw({0, 0}, p, q)==0){
        if (p.first==q.first) return p.second < q.second;
        return p.first < q.first;
    }
    return ccw({0, 0}, p, q) > 0;
}

vector<pair<int, int>> gethull(vector<pair<int, int>> P){
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());

    vector<pair<int, int>> ret;
    int ox = 1e9, oy = 1e9;
    for (auto &p:P) if (oy>p.second || (oy==p.second && ox>p.first)){
        ox = p.first, oy = p.second;
    }

    ret.emplace_back(0, 0);
    for (auto &p:P) if (ox!=p.first || oy!=p.second) ret.emplace_back(p.first-ox, p.second-oy);
    sort(ret.begin()+1, ret.end(), cmp);

    vector<pair<int, int>> ret2;
    ret2.emplace_back(ox, oy);
    for (int i=1;i<(int)ret.size();i++){
        while(ret2.size()>1){
            auto s = ret2.back(); ret2.pop_back();
            auto f = ret2.back();
            if (ccw(f, s, ret[i])>0) {ret2.push_back(s); break;}
        }
        ret2.emplace_back(ret[i].first+ox, ret[i].second+oy);
    }
    return ret2;
}

int main(){
    scanf("%d %d", &n, &S);
    vector<pair<int, int>> P;
    for (int i=1;i<=n;i++){
        scanf("%d %d %d %d", A+i, B+i, C+i, D+i);
        P.emplace_back(A[i], B[i]);
        P.emplace_back(C[i], D[i]);
    }
    P.emplace_back(S, S);
    P.emplace_back(S, -S);
    P.emplace_back(-S, S);
    P.emplace_back(-S, -S);

    auto Q = gethull(P);
    //for (auto &p:Q) printf(" %d %d\n", p.first, p.second);

    double ans = 0;
    for (int i=0;i<(int)Q.size();i++){
        int j = i+1;
        if (j==(int)Q.size()) j = 0;

        if (ccw(Q[i], Q[j], {A[1], B[1]})==0 && ccw(Q[i], Q[j], {C[1], D[1]})==0) ans -= dist({A[1], B[1]}, {C[1], D[1]});
        ans += dist(Q[i], Q[j]);
    }
    printf("%.15f\n", min(ans, (double)S*8));
    return 0;
}

Compilation message

fences.cpp: In function 'int main()':
fences.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d", &n, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fences.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d %d %d", A+i, B+i, C+i, D+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -