QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797964#5809. Min PerimeterBananaMac20 ✓9860ms66452kbC++2014.2kb2024-12-03 21:58:212024-12-03 21:58:21

Judging History

你现在查看的是最新测评结果

  • [2024-12-03 21:58:21]
  • 评测
  • 测评结果:20
  • 用时:9860ms
  • 内存:66452kb
  • [2024-12-03 21:58:21]
  • 提交

answer

/**
 * 15:15:28 9/27/24
 * Point
 */
// ./ICPC/Geometry/OrganizedTemplates/Point.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define uint unsigned int
#define double long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define nl '\n'
#define all(v) v.begin(), v.end()
#define NO (cout << "NO" << nl);
#define YES (cout << "YES" << nl);
#define F first
#define S second
#define INF LONG_LONG_MAX
#define pii pair<int, int>
#define vec vector
#define LT int T; cin >> T; while (T--)
template<typename T>
using vec2d = vector<vector<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using indexed_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

namespace Geometry {
    using ftype = double;
    using atype = double;
    const double eps = 1e-9l;
    const double pi = acos(-1.0l);
//    const double e = exp(1.0L);
    const double inf = 1e18l;
    const int mod = 1e9 + 7;
    const int iinf = LONG_LONG_MAX;
    int32_t prec = 25;
    bool useDoubleIn = false;

    ftype sqr(ftype v) { return v * v; }

    void setPrec(ostream& out = cout) {
        out << fixed << setprecision(prec);
    }

    //bool eq(const ftype& a, const ftype& b) {
    //    return a == b;
    //}
    bool eq(const ftype& a, const ftype& b) {
        return abs(a - b) < eps;
    }

    //bool ls(const ftype& a, const ftype& b) {
    //    return a < b;
    //}
    bool ls(const ftype& a, const ftype& b) {
        return (b - a) > eps;
    }

    //bool lse(const ftype& a, const ftype& b) {
    //    return a <= b;
    //}
    bool lse(const ftype& a, const ftype& b) {
        return ls(a, b) or eq(a, b);
    }

    //bool bt(const ftype& a, const ftype& b, const ftype& c) {
    //    return a < b and b < c;
    //}
    bool bt(const ftype& a, const ftype& b, const ftype& c) {
        return ls(a, b) and ls(b, c);
    }

    //bool bte(const ftype& a, const ftype& b, const ftype& c) {
    //    return a <= b and b <= c;
    //}
    bool bte(const ftype& a, const ftype& b, const ftype& c) {
        return lse(a, b) and lse(b, c);
    }

    ftype max(const ftype& a, const ftype& b) {
        return ls(a, b) ? b : a;
    }

    int max(int a, int b) {
        return a < b ? b : a;
    }

    ftype min(const ftype& a, const ftype& b) {
        return ls(a, b) ? a : b;
    }

    int min(int a, int b) {
        return a < b ? a : b;
    }

    optional<array<ftype, 2>> quadratic(ftype a, ftype b, ftype c) {
        ftype discriminant = b * b - 4 * a * c;
        if (ls(discriminant, 0)) {
            return nullopt;
        }
        ftype sqrtD = sqrt(discriminant);
        return array<ftype, 2>{(-b + sqrtD) / (2 * a), (-b - sqrtD) / (2 * a)};
    }

    // Returns angle with respect to the x-axis.
    atype angle(atype x, atype y) {
        return atan2(y, x);
    }
    atype torad(atype a) { return a / 180 * pi; }
    atype todeg(atype a) { return a / pi * 180; }

    int sign(const ftype& v) {
        if (ls(0, v)) return 1;
        else if (ls(v, 0)) return -1;
        return 0;
    }

    pair<int, int> reduce(ftype v0, ftype v1) {
        // log(n)
        int a = (int)v0, b = (int)v1;
        if (a == 0) return {0, sign(b)};
        if (b == 0) return {sign(a) * iinf, 0};
        int g = gcd(a, b);
        return {a / g, b / g};
    }

    pair<int, int> reducef(ftype v0, ftype v1) {
        // log(n)
        return reduce(v0 * 1e6l, v1 * 1e6l);
    }

    // 2D point
    struct P {
        ftype x, y;
        static P polar(const ftype& r, const atype& a) {
            return {r * cos(a), r * sin(a)};
        }
        P(): x{0}, y{0} {}
        P(ftype x, ftype y): x{x}, y{y} {}
        explicit P(const complex<ftype>& p): P(p.real(), p.imag()) {}
        explicit P(const pair<ftype, ftype>& p): P(p.F, p.S) {}
        P(const P& p): P(p.x, p.y) {}
        explicit operator complex<ftype>() const {
            return {x, y};
        }
        explicit operator pair<ftype, ftype>() const {
            return {x, y};
        }
        ftype dist(const P& p) const {
            return (*this - p).abs();
        }
        ftype dist2(const P& p) const {
            return (*this - p).norm();
        }
        atype r() const {
            return hypot(x, y);
        }
        atype a() const {
            return Geometry::angle(x, y);
        }
        atype ua(const P& p) const {
            // undirected angle
            double v0 = fabs(a() - p.a()), v1 = fabs(p.ap() - ap());
            if (ls(v0, v1)) return v0;
            else return v1;
        }
        atype ap() const {
            atype res = Geometry::angle(x, y);
            if (res < 0) res += 2 * pi;
            return res;
        }
        atype angle(const P& p) const {
            return acos(dot(p) / (abs() * p.abs()));
        }
        P operator-() const {
            return *this * -1;
        }
        P operator+() const {
            return *this;
        }
        P operator+=(const P& p) {
            x += p.x;
            y += p.y;
            return *this;
        }
        P operator-=(const P& p) {
            x -= p.x;
            y -= p.y;
            return *this;
        }
        P operator*=(const ftype& v) {
            x *= v;
            y *= v;
            return *this;
        }
        P operator/=(const ftype& v) {
            x /= v;
            y /= v;
            return *this;
        }
        P operator%=(const ftype& v) {
            x = fmod(x, v);
            y = fmod(y, v);
            return *this;
        }
        P operator^=(const ftype& an) {
            return *this = rotateccw(an);
        }
        P operator|=(const ftype& an) {
            return *this = rotatecw(an);
        }
        P operator|(const ftype& an) {
            P res = *this;
            res |= an;
            return res;
        }
        P operator^(const ftype& an) {
            P res = *this;
            res ^= an;
            return res;
        }
        P operator+(const P& p) const {
            P res = *this;
            res += p;
            return res;
        }
        P operator-(const P& p) const {
            P res = *this;
            res -= p;
            return res;
        }
        P operator*(const ftype& v) const {
            P res = *this;
            res *= v;
            return res;
        }
        P operator/(const ftype& v) const {
            P res = *this;
            res /= v;
            return res;
        }
        P operator%(const ftype& v) const {
            P res = *this;
            res %= v;
            return res;
        }
        bool operator==(const P& p) const {
            return eq(x, p.x) and eq(y, p.y);
        }
        bool operator<(const P& p) const {
            return eq(p.x, x) ? ls(y, p.y) : ls(x, p.x);
        }
        bool ycmp(const P& p) const {
            return eq(p.y, y) ? ls(x, p.x) : ls(y, p.y);
        }
        bool operator<=(const P& p) const {
            return *this < p or *this == p;
        }
        ftype slope() const {
            return y / x;
        }
        pair<int, int> fslope() const {
            return reduce(y, x);
        }
        pair<int, int> inorm() const {
            return reduce(x, y);
        }
        ftype cross(const P& b, const P& c) const {
            return (b - *this).cross(c - *this);
        }
        bool is_point_in_angle(P b, const P& a, P c) const {
            // does point p lie in angle <bac
            assert(c.orientation(a, b) != 0);
            if (a.orientation(c, b) < 0) swap(b, c);
            return a.orientation(c, *this) >= 0 && a.orientation(b, *this) <= 0;
        }
        // 1 this is to right of ab, 0 collinear, -1 to left
        int orientation(const P& a, const P& b) const {
            // orientation of this with respect to AB
            const P& c = *this;
            ftype d = (b - c).cross(a - c);
            return sign(d);
        }
        ftype cross(const P& p) const {
            return x * p.y - y * p.x;
        }
        ftype dot(const P& p) const {
            return x * p.x + y * p.y;
        }
        ftype dot(const P& a, const P& b) const {
            return (a - *this).dot(b - *this);
        }
        ftype norm() const {
            return dot(*this);
        }
        atype abs() const {
            return sqrt((atype)norm());
        }
        P truncate(ftype v) const {
            // returns a vector with norm v and having same direction
            ftype k = abs();
            if (sign(k) == 0) return *this;
            v /= k;
            return *this * v;
        }
        P normalize() const {
            return truncate(1);
        }
        P normal_l() const {
            return {-y, x};
        }
        P normal_r() const {
            return {y, -x};
        }
        P normal_lfs() const {
            return P(fslope()).normal_l();
        }
        P normal_rfs() const {
            return P(fslope()).normal_r();
        }
        P rotateccw(const atype& angle, const P& ref = {0, 0}) const {
            P res;
            ftype xs = x - ref.x, ys = y - ref.y;
            res.x = ref.x + (xs * cos(angle) - ys * sin(angle));
            res.y = ref.y + (xs * sin(angle) + ys * cos(angle));
            return res;
        }
        P rotatecw(const atype& angle, const P& ref = {0, 0}) const {
            return rotateccw(-angle, ref);
        }
        friend P operator*(const ftype& v, const P& p) {
            return p * v;
        }
        friend istream& operator>>(istream& in, P& p) {
            if (useDoubleIn) {
                return in >> p.x >> p.y;
            }

            int xv, yv;
            in >> xv >> yv;
            p = P(xv, yv);
            return in;
        }
        friend ostream& operator<<(ostream& out, const P& p) {
            setPrec(out);
            return out << "(" << p.x << ", " << p.y << ")";
        }
    };

    // basic comparison functions
    auto angleCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.a(), p1.a());
    };
    auto radiusCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.r(), p1.r());
    };
    auto stdCmp = [](const P& p0, const P& p1) -> bool {
        return p0 < p1;
    };
    auto xCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.x, p1.x);
    };
    auto yCmp = [](const P& p0, const P& p1) -> bool {
        return ls(p0.y, p1.y);
    };

    // Hash function
    struct p_hash {
        static __int128 splitmix128(__int128 x) {
            // gr = 0x9e3779b97f4a7c15f39cc0605cedc835
            // c0 = 0xbf58476d1ce4e5b9a3f7b72c1e3c9e3b
            // c1 = 0x94d049bb133111ebb4093822299f31d7
            __int128 gr = 0x9e3779b97f4a7c15, c0 = 0xbf58476d1ce4e5b9, c1 = 0x94d049bb133111eb;
            gr <<= 64;
            c0 <<= 64;
            c1 <<= 64;
            gr += 0xf39cc0605cedc835;
            c0 += 0xa3f7b72c1e3c9e3b;
            c1 += 0xb4093822299f31d7;
            x += gr;
            x = (x ^ (x >> 62)) * c0;
            x = (x ^ (x >> 59)) * c1;
            return x ^ (x >> 63);
        }

        size_t operator()(const P& p) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            __int128 x = (((__int128)p.x) << 64) | ((__int128)p.y);
            return splitmix128(x + FIXED_RANDOM);
        }
    };

    P inf_pt{inf, inf};

    double heron(const P& p1, const P& p2, const P& p3) {
        double a = p1.dist(p2);
        double b = p1.dist(p3);
        double c = p3.dist(p2);
        double s = (a+b+c)/2.0;
        double area = sqrt( s*(s-a)*(s-b)*(s-c) );
        return area;
    }

    bool isCollinear(const P& a, const P& b, const P& c) {
        return eq(0, heron(a, b, c));
    }
}
using namespace Geometry;


ftype minper;
vec<P> btr;
int n;
vec<P> a, t;

bool cmp_x(const P& p0, const P& p1) {
    return p0 < p1;
}

bool cmp_y(const P& p0, const P& p1) {
    return ls(p0.y, p1.y);
}

void upd_ans_t(const P& p0, const P& p1, const P& p2) {
    ftype per = p0.dist(p1) + p0.dist(p2) + p1.dist(p2);
    if (ls(per, minper)) {
        minper = per;
        btr = {p0, p1, p2};
    }
}

void rec_t(int l, int r) {
    if (r - l <= 3) {
        // Check all triangles in this small range
        for (int i = l; i < r; ++i) {
            for (int j = i + 1; j < r; ++j) {
                for (int k = j + 1; k < r; ++k) {
                    upd_ans_t(a[i], a[j], a[k]);
                }
            }
        }
        sort(a.begin() + l, a.begin() + r, cmp_y);
        return;
    }

    int m = (l + r) >> 1;
    ftype midx = a[m].x;
    rec_t(l, m);
    rec_t(m, r);

    merge(a.begin() + l, a.begin() + m, a.begin() + m, a.begin() + r, t.begin(), cmp_y);
    copy(t.begin(), t.begin() + r - l, a.begin() + l);

    vec<P> strip;
    for (int i = l; i < r; ++i) {
        if (ls(abs(a[i].x - midx), minper / 2)) {
            for (int j = (int)strip.size() - 1; j >= 0 && ls(a[i].y - strip[j].y, minper / 2); --j) {
                for (int k = j - 1; k >= 0 && ls(a[i].y - strip[k].y, minper / 2); --k) {
                    upd_ans_t(a[i], strip[j], strip[k]);
                }
            }
            strip.push_back(a[i]);
        }
    }
}

void find_mn_t() {
    t.resize(n);
    sort(all(a), cmp_x);
    minper = 1e20;
    rec_t(0, n);
}


void solve() {
    cin >> n;
    a.resize(n);
    for (P& p: a) cin >> p;
    find_mn_t();
    cout << setprecision(25) << fixed << minper << nl;
}

int32_t main() {
    fast
    const string NAME{" "};
    if (NAME != " ") {
        freopen((NAME + ".in").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    int T, tt;
    cin >> T; tt = T;
    while (T--) {
        cout << "Case #" << tt - T << ": ";
        solve();
    }
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 56ms
memory: 4180kb

input:

15
3
2 6
7 0
3 0
3
713 269
371 79
455 421
3
91983245 637281504
756917015 312173515
869576338 436726680
10000
14761642 78236002
9047458 47951098
5238002 27761162
476182 2523742
1428546 7571226
26190010 138805810
21904372 116092132
18094916 95902196
43332562 229660522
55237112 292754072
52380020 27761...

output:

Case #1: 17.8930122062048740823325677
Case #2: 1042.8448349643881045700766208
Case #3: 1711142102.7913271078141406178474426
Case #4: 90912.2963740329243265136938135
Case #5: 3.4142135623730950487637881
Case #6: 26.1538303421636949327305777
Case #7: 1701.0126810956169113309144336
Case #8: 2865438.191...

result:

ok correct! (15 test cases)

Subtask #2:

score: 15
Accepted

Test #2:

score: 15
Accepted
time: 9860ms
memory: 66452kb

input:

15
3
501691275 344354353
167768963 536043860
249445040 557426549
4
1000000000 0
0 0
1000000000 1000000000
0 1000000000
1000000
138925776 669369648
61257680 295150640
170762328 822763944
55483472 267329456
97736936 470914328
84041848 404928904
18463588 88960924
124429360 599523280
95066048 458045504
...

output:

Case #1: 799653579.1330897417501546442508698
Case #2: 3414213562.3730950488243252038955688
Case #3: 866.0715905743589277943073057
Case #4: 62459.8953696371481782989576459
Case #5: 59141.9183589317811033936322929
Case #6: 898195.0909682679932757309870794
Case #7: 1707085.7699867850540158542571589
Cas...

result:

ok correct! (15 test cases)

Extra Test:

score: 0
Extra Test Passed