oj.uz

Submission #584928

# Submission time Handle Problem Language Result Execution time Memory
584928 2022-06-28T06:56:04 Z 반딧불(#8380) Fences (JOI18_fences) C++17
0 / 100
 10 ms 300 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

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

    vector2 operator*(const double &r)const{
        return vector2(x*r, y*r);
    }

    vector2 operator/(const double &r)const{
        return vector2(x/r, y/r);
    }

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

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

    double 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));
    }
};

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

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

int n;
ll s;
vector2 a, b;
double ans=1e18;

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]) < -1e-9) ret.pop_back();
        ret.push_back(vec[i]);
    }
    return ret;
}

void calc(vector2 a, vector2 b){
    vector<vector2> h = hull({a, b, vector2(s, s), vector2(s, -s), vector2(-s, s), vector2(-s, -s)});
    double sum = 0;
    for(int i=0; i<(int)h.size(); i++){
        auto A = h[i], B = h[(i+1)%(int)h.size()];
        sum += A.dist(B);
        if(abs(ccw(A, a, b)) <= 1e-9 && abs(ccw(B, a, b)) <= 1e-9){
            if(max(min(A, B), min(a, b)) <= min(max(A, B), max(a, b)))
                sum -= max(min(A, B), min(a, b)).dist(min(max(A, B), max(a, b)));
        }
    }
    sum = min(sum, double(s)*8);
    ans = min(sum, ans);
}

vector2 getPoint(vector2 a, vector2 b, vector2 targ){
    for(int cnt=0; cnt<=100000; cnt++){
        vector2 p = (a+a+b)/3, q = (a+b+b)/3;
        if(targ.dist(p) < targ.dist(q)) b = q;
        else a = p;
    }
    return a;
}

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

    vector<vector2> endpoints = {a, b};
    endpoints.push_back(getPoint(a, b, vector2(s, s)));
    endpoints.push_back(getPoint(a, b, vector2(s, -s)));
    endpoints.push_back(getPoint(a, b, vector2(-s, s)));
    endpoints.push_back(getPoint(a, b, vector2(-s, -s)));

    for(auto e1: endpoints) for(auto e2: endpoints) calc(e1, e2);
    printf("%.9f", ans);
}

Compilation message

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

Subtask #1
0 / 18.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 49.0

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