Cerinta completa

In this problem you operate on two arrays of integers. We will call them the and the respectively.
Your goal is just to maintain them under the modification operations, such as:

  • 1 : Reverse the subarray of the array, starting at the number, ending at the number, inclusively;
  • 2 : Swap two consecutive fragments of the array, the first is from the number to the , the second is from the number to the ;
  • 3 : Swap the piece that starts at the number and end at the one between the and the array;
  • 4 : We consider only the piece from the number to the one. The numbers in the array are -coordinates of some set of points and the numbers in the array are -coordinates of them. For the obtained set of points we would like to place such a circle on a plane that would contain all the points in it and would have the minimal radius. Find this minimal radius.

Input Format
The first line of input contains two space separated integers and denoting the number of integers in arrays and the number of queries respectively.
The second line contains space separated integers: the initial elements of the array.
The third line contains space separated integers: the initial elements of the array.
Then there are lines containing queries in the format listed above.

Output Format
For each type-4 query output the sought minimal radius with exactly two symbols after the decimal point precision.

Constraints

All the numbers in arrays are non-negative and don’t exceed .
The sum of over the type-4 queries won’t exceed .
In the query of the type 2, .
In the queries of the types 1, 3, 4, ; .

Sample Input

10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
3 2 6
1 0 9 9
4 6 9
2 0 2 7 9 9
1 0 3 6
2 1 2 3 4 5
1 1 7 10
2 1 8 8 9 10
4 6 9
2 0 2 2 4 6

Example Output

2.12
2.50

Limbajul de programare folosit: cpp14

Cod:

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

struct Node {
    int v;
    uint32_t pr;
    int sz;
    bool rev;
    Node* l;
    Node* r;
    Node(int _v, uint32_t _pr) : v(_v), pr(_pr), sz(1), rev(false), l(nullptr), r(nullptr) {}
};

static inline int getsz(Node* t) { return t ? t->sz : 0; }

static inline void pull(Node* t) {
    if (!t) return;
    t->sz = 1 + getsz(t->l) + getsz(t->r);
}

static inline void push(Node* t) {
    if (!t || !t->rev) return;
    t->rev = false;
    swap(t->l, t->r);
    if (t->l) t->l->rev = !t->l->rev;
    if (t->r) t->r->rev = !t->r->rev;
}

void split(Node* t, int k, Node*& a, Node*& b) {
    if (!t) {
        a = b = nullptr;
        return;
    }
    push(t);
    int ls = getsz(t->l);
    if (k <= ls) {
        split(t->l, k, a, t->l);
        b = t;
        pull(b);
    } else {
        split(t->r, k - ls - 1, t->r, b);
        a = t;
        pull(a);
    }
}

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->pr > b->pr) {
        push(a);
        a->r = merge(a->r, b);
        pull(a);
        return a;
    }
    push(b);
    b->l = merge(a, b->l);
    pull(b);
    return b;
}

void collect(Node* t, vector<int>& out) {
    if (!t) return;
    push(t);
    collect(t->l, out);
    out.push_back(t->v);
    collect(t->r, out);
}

struct Circle {
    long double x;
    long double y;
    long double r2;
    bool ok;
};

struct Pt {
    long double x;
    long double y;
};

static inline long double dist2(long double x1, long double y1, long double x2, long double y2) {
    long double dx = x1 - x2;
    long double dy = y1 - y2;
    return dx * dx + dy * dy;
}

static inline bool inside(const Circle& c, const Pt& p) {
    if (!c.ok) return false;
    return dist2(c.x, c.y, p.x, p.y) <= c.r2 + 1e-12L;
}

Circle circle_two(const Pt& a, const Pt& b) {
    long double cx = (a.x + b.x) * 0.5L;
    long double cy = (a.y + b.y) * 0.5L;
    return {cx, cy, dist2(cx, cy, a.x, a.y), true};
}

Circle circle_three(const Pt& a, const Pt& b, const Pt& c) {
    long double d = 2.0L * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
    if (fabsl(d) < 1e-18L) {
        Circle best = circle_two(a, b);
        Circle c2 = circle_two(a, c);
        Circle c3 = circle_two(b, c);
        if (c2.r2 > best.r2) best = c2;
        if (c3.r2 > best.r2) best = c3;
        return best;
    }
    long double aa = a.x * a.x + a.y * a.y;
    long double bb = b.x * b.x + b.y * b.y;
    long double cc = c.x * c.x + c.y * c.y;
    long double ux = (aa * (b.y - c.y) + bb * (c.y - a.y) + cc * (a.y - b.y)) / d;
    long double uy = (aa * (c.x - b.x) + bb * (a.x - c.x) + cc * (b.x - a.x)) / d;
    return {ux, uy, dist2(ux, uy, a.x, a.y), true};
}

long double minimum_enclosing_radius(vector<Pt>& pts, mt19937_64& rng) {
    if (pts.empty() || pts.size() == 1) return 0.0L;
    shuffle(pts.begin(), pts.end(), rng);

    Circle c{0, 0, 0, false};
    int n = (int)pts.size();

    for (int i = 0; i < n; ++i) {
        if (inside(c, pts[i])) continue;
        c = {pts[i].x, pts[i].y, 0.0L, true};
        for (int j = 0; j < i; ++j) {
            if (inside(c, pts[j])) continue;
            c = circle_two(pts[i], pts[j]);
            for (int k = 0; k < j; ++k) {
                if (inside(c, pts[k])) continue;
                c = circle_three(pts[i], pts[j], pts[k]);
            }
        }
    }
    return sqrt(max((long double)0.0, c.r2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    mt19937 rng(712367);
    mt19937_64 mec_rng(19260817);

    Node* roots[2] = {nullptr, nullptr};

    for (int id = 0; id < 2; ++id) {
        for (int i = 0; i < N; ++i) {
            int x;
            cin >> x;
            roots[id] = merge(roots[id], new Node(x, rng()));
        }
    }

    vector<int> xs, ys;
    vector<Pt> pts;

    for (int qi = 0; qi < M; ++qi) {
        int tp;
        cin >> tp;

        if (tp == 1) {
            int id, l, r;
            cin >> id >> l >> r;
            Node *a, *b, *c;
            split(roots[id], r, b, c);
            split(b, l - 1, a, b);
            if (b) b->rev = !b->rev;
            roots[id] = merge(merge(a, b), c);
        } else if (tp == 2) {
            int id, l1, r1, l2, r2;
            cin >> id >> l1 >> r1 >> l2 >> r2;
            Node *a, *b, *c, *d, *e;
            Node *t1, *t2, *t3;

            split(roots[id], r2, t1, e);         // [1..r2], [r2+1..]
            split(t1, l2 - 1, t2, d);            // [1..l2-1], [l2..r2]
            split(t2, r1, t3, c);                // [1..r1], [r1+1..l2-1]
            split(t3, l1 - 1, a, b);             // [1..l1-1], [l1..r1]

            roots[id] = merge(a, merge(d, merge(c, merge(b, e))));
        } else if (tp == 3) {
            int l, r;
            cin >> l >> r;

            Node *a0, *b0, *c0, *t0;
            Node *a1, *b1, *c1, *t1;

            split(roots[0], r, t0, c0);
            split(t0, l - 1, a0, b0);

            split(roots[1], r, t1, c1);
            split(t1, l - 1, a1, b1);

            swap(b0, b1);

            roots[0] = merge(a0, merge(b0, c0));
            roots[1] = merge(a1, merge(b1, c1));
        } else {
            int l, r;
            cin >> l >> r;

            Node *a0, *b0, *c0, *t0;
            Node *a1, *b1, *c1, *t1;

            split(roots[0], r, t0, c0);
            split(t0, l - 1, a0, b0);

            split(roots[1], r, t1, c1);
            split(t1, l - 1, a1, b1);

            xs.clear();
            ys.clear();
            collect(b0, xs);
            collect(b1, ys);

            pts.clear();
            pts.reserve(xs.size());
            for (size_t i = 0; i < xs.size(); ++i) {
                pts.push_back(Pt{(long double)xs[i], (long double)ys[i]});
            }

            long double ans = minimum_enclosing_radius(pts, mec_rng);
            if (fabsl(ans) < 0.0005L) ans = 0.0L;
            cout << fixed << setprecision(2) << (double)ans << '\n';

            roots[0] = merge(a0, merge(b0, c0));
            roots[1] = merge(a1, merge(b1, c1));
        }
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464671411

Link challenge: https://www.hackerrank.com/challenges/weird-queries/problem

Two Array Problem