oj.uz

Submission #584860

# Submission time Handle Problem Language Result Execution time Memory
584860 2022-06-28T05:32:45 Z 반딧불(#8380) Fences (JOI18_fences) C++17
0 / 100
 1 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);
    }

    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]) <= 0) 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++){
        sum += h[i].dist(h[(i+1)%(int)h.size()]);
    }
    sum -= a.dist(b);
    sum = min(sum, double(s)*8);
    ans = min(sum, ans);
}

vector2 getPointX(vector2 a, vector2 b, double x){
    if(a.x == b.x) return a;
    return (b*(x-a.x)+a*(b.x-x)) / (b.x-a.x);
}

vector2 getPointY(vector2 a, vector2 b, double y){
    if(a.y == b.y) return a;
    return (b*(y-a.y)+a*(b.y-y)) / (b.y-a.y);
}

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};
    if(a.x > b.x) swap(a, b);
    if(a.x <= -s && -s <= b.x){
        endpoints.push_back(getPointX(a, b, -s));
    }
    if(a.x <= s && s <= b.x){
        endpoints.push_back(getPointX(a, b, s));
    }

    if(a.y > b.y) swap(a, b);
    if(a.y <= -s && -s <= b.y){
        endpoints.push_back(getPointY(a, b, -s));
    }
    if(a.y <= s && s <= b.y){
        endpoints.push_back(getPointY(a, b, 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:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %lld", &n, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
fences.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -