oj.uz

Submission #584850

# Submission time Handle Problem Language Result Execution time Memory
584850 2022-06-28T05:20:36 Z 반딧불(#8380) Fences (JOI18_fences) C++17
0 / 100
 1 ms 304 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct vector2{
    ll x, y;
    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}

    vector2 operator-(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    bool operator<(const vector2 &r)const{
        return make_pair(x, y) < make_pair(r.x, r.y);
    }

    ll cross(vector2 &r)const{
        return x*r.y - y*r.x;
    }

    double dist(vector2 &r)const{
        return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}

ll ccw(vector2 a, vector2 b, vector2 c){
    return ccw(b-a, c-a);
}

int n;
ll s;
vector2 a, b;
double ans;

vector<vector2> hull(vector<vector2> vec){
    vector<vector2> ret;
    sort(vec.begin(), vec.end());
    ret.push_back(vec[0]);
    sort(vec.begin()+1, vec.end(), [&](vector2 &A, vector2 &B){
        return ccw(A, vec[0], B) < 0;
    });
    for(int i=1; i<(int)vec.size(); i++){
        while((int)ret.size() >= 2 && ccw(ret[(int)ret.size()-2], ret.back(), vec[i]) <= 0) ret.pop_back();
        ret.push_back(vec[i]);
    }
    return ret;
}

int main(){
    scanf("%d %lld", &n, &s);
    scanf("%lld %lld %lld %lld", &a.x, &a.y, &b.x, &b.y);

    vector<vector2> h = hull({a, b, vector2(s, s), vector2(s, -s), vector2(-s, s), vector2(-s, -s)});
    for(int i=0; i<(int)h.size(); i++){
        ans += h[i].dist(h[(i+1)%(int)h.size()]);
    }
    ans -= a.dist(b);
    ans = min(ans, double(s)*8);
    printf("%.9f", ans);
}

Compilation message

fences.cpp: In function 'int main()':
fences.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %lld", &n, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
fences.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld %lld %lld %lld", &a.x, &a.y, &b.x, &b.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 1 ms 304 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 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 1 ms 304 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 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 1 ms 304 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -