Submission #892744

#	Time	Username	Problem	Language	Result	Execution time	Memory
892744		box	Fences (JOI18_fences)	C++17	0 / 100	0 ms	348 KiB

fences

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using T = double;

const int N = 105;
const T eps = 1e-9;

struct point {
    T x, y;
};

point operator-(const point p, const point q) {
    return {p.x - q.x, p.y - q.y};
}

double norm(const point p) {
    return sqrt(p.x * p.x + p.y * p.y);
}

double dist(const point p, const point q) {
    return norm(p - q);
}

T cross(const point p, const point q) {
    return p.x * q.y - p.y * q.x;
}

int sign(const T x) {
    return (x > eps) - (x < eps);
}

int dir(const point p, const point q, const point r) {
    return sign(cross(q - p, r - p));
}

bool same(const T x, const T y) {
    return abs(x - y) <= eps;
}
bool same(const point p, const point q) {
    return same(p.x, q.x) && same(p.y, q.y); 
}

void read(point &p) {
    static int x;
    cin >> x;
    p.x = x;
    cin >> x;
    p.y = x;
}

struct seg {
    point p, q;
};

bool isect(const seg one, const seg two) {
    if (same(one.p, two.p) || same(one.p, two.q) || same(one.q, two.p) || same(one.q, two.q)) return false;
    int x = dir(one.p, one.q, two.p);
    int y = dir(one.p, one.q, two.q);
    if (x == 0 || y == 0) return false;
    return x != y;
}

double area(const point p, const point q, const point r) {
    return abs(cross(p, q) + cross(q, r) + cross(r, p));
}

double dist(const seg s, const point p) {
    if (same(s.p, s.q)) return dist(p, s.p);
    return area(s.p, s.q, p) / dist(s.p, s.q);
}

int n; double s;
seg v[N];
point rect[4];
double ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        read(v[i].p);
        read(v[i].q);
    }
    if (n > 1) return 0;
    ans = s * 8;
    rect[0] = {s, s};
    rect[1] = {s, -s};
    rect[2] = {-s, -s};
    rect[3] = {-s, s};
    for (int rep = 0; rep < 2; rep++) {
        for (int i = 0; i < 4; i++)
            ans = min(ans, s * 12 + dist(v[0].p, rect[i]) + dist(rect[(i + 1) % 4], v[0].q));
        swap(v[0].p, v[0].q);
    }
    cout << fixed << setprecision(12) << ans << endl;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 33
• Subtask 3: 0 / 49