Header Ad

HackerRank Two Array Problem solution

In this HackerRank Two Array Problem solution, we are given two arrays of N integers. we need to perform some modification operations on that.

HackerRank Two Array Problem solution


Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    static class Vec {
        double x, y;

        Vec() {
        }

        Vec(double x, double y) {
            this.x = x;
            this.y = y;
        }

        Vec add(Vec q) {
            return new Vec(x + q.x, y + q.y);
        }

        Vec minus(Vec q) {
            return new Vec(x - q.x, y - q.y);
        }

        Vec mult(double t) {
            return new Vec(x * t, y * t);
        }

        Vec div(double t) {
            return new Vec(x / t, y / t);
        }

        double mult(Vec q) {
            return x * q.x + y * q.y;
        }

        double modulo(Vec q) {
            return x * q.y - y * q.x;
        }
    }

    static final int N = 100000;
    static final int V = (N + 2) * 2;

    static Vec[] a;

    static double hypot(double x, double y) {
        return Math.sqrt(x * x + y * y);
    }

    static double abs(Vec p) {
        return hypot(p.x, p.y);
    }

    static class Circle {
        double x, y, r;

        Circle(double x, double y, double r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }

        Circle(Vec a, double r) {
            this.x = a.x;
            this.y = a.y;
            this.r = r;
        }
    }

    static boolean inCircle(Circle c, Vec a) {
        return hypot(a.x - c.x, a.y - c.y) <= c.r;
    }

    static Vec circumcenter(Vec p, Vec q, Vec r) {
        Vec a = p.minus(r);
        Vec b = q.minus(r);
        Vec c = new Vec(a.mult(p.add(r)) / 2, b.mult(q.add(r)) / 2);
        Vec x = new Vec(a.x, b.x);
        Vec tmp = new Vec(c.modulo(new Vec(a.y, b.y)), x.modulo(c));
        return tmp.div(a.modulo(b));
    }

    static Circle smallestEnclosingCircle(int n) {
        Circle C = new Circle(0, 0, -1);
        for (int i = 0; i < n; i++) {
            if (!inCircle(C, a[i])) {
                C = new Circle(a[i], 0);
                for (int j = 0; j < i; j++) {
                    if (!inCircle(C, a[j])) {
                        C = new Circle((a[i].add(a[j])).div(2), abs(a[i].minus(a[j])) / 2);
                        for (int k = 0; k < j; k++) {
                            if (!inCircle(C, a[k])) {
                                Vec o = circumcenter(a[i], a[j], a[k]);
                                C = new Circle(o, abs(o.minus(a[k])));
                            }
                        }
                    }
                }
            }
        }
        return C;
    }

    static int[] y = new int[N];
    static int ny;

    static class Node {
        boolean flp;
        Node l, r;
        int key, size;

        void init(int k, int s) {
            flp = false;
            key = k;
            size = s;
            l = r = nodeNull;
        }

        int cmp(int k) {
            if (l.size == k) {
                return -1;
            }
            return l.size < k ? 1 : 0;
        }

        void mconcat() {
            size = l.size + 1 + r.size;
        }

        void untag() {
            if (flp) {
                flp = false;
                l.flip();
                r.flip();
            }
        }

        void flip() {
            if (this == nodeNull) {
                return;
            }
            Node tmp = l;
            l = r;
            r = tmp;
            flp = !flp;
        }
    }

    static Node[] pool = new Node[V];
    static int allo = 0;
    static Node nodeNull = new Node();

    static Node splay(Node x, int k) {
        Node lspine = nodeNull;
        Node rspine = nodeNull;
        for (;;) {
            x.untag();
            if (x.l.size == k) {
                break;
            }

            if (x.l.size < k) {
                k -= x.l.size + 1;
                Node y = x.r;
                y.untag();
                if (x.r.cmp(k) == 1) {
                    k -= x.r.l.size + 1;
                    x.r = y.l;
                    y.l = x;
                    x.mconcat();
                    x = y.r;
                    y.r = lspine;
                    lspine = y;
                } else {
                    x.r = lspine;
                    lspine = x;
                    x = y;
                }
            } else {
                Node y = x.l;
                y.untag();
                if (x.l.cmp(k) == 0) {
                    x.l = y.r;
                    y.r = x;
                    x.mconcat();
                    x = y.l;
                    y.l = rspine;
                    rspine = y;
                } else {
                    x.l = rspine;
                    rspine = x;
                    x = y;
                }
            }
        }

        {
            Node z = x.l;
            while (lspine != nodeNull) {
                Node y = lspine.r;
                lspine.r = z;
                lspine.mconcat();
                z = lspine;
                lspine = y;
            }
            x.l = z;
        }

        {
            Node z = x.r;
            while (rspine != nodeNull) {
                Node y = rspine.l;
                rspine.l = z;
                rspine.mconcat();
                z = rspine;
                rspine = y;
            }
            x.r = z;
        }
        x.mconcat();
        return x;
    }

    static Node range(Node rt, int L, int R) {
        rt = splay(rt, L - 1);
        rt.r = splay(rt.r, R - L);
        return rt;
    }

    static void inorder(Node rt, int d) {
        if (rt != nodeNull) {
            rt.untag();
            inorder(rt.l, d + 1);
            y[ny++] = rt.key;
            inorder(rt.r, d + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < pool.length; i++) {
            pool[i] = new Node();
        }
        a = new Vec[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = new Vec();
        }
        Node[] rt = { pool[allo++], pool[allo++] };
        nodeNull.init(0, 0);
        for (int d = 0; d < 2; d++) {
            rt[d].init(-1, 1);
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i <= n; i++) {
                Node node = pool[allo];
                if (i < n) {
                    int item = Integer.parseInt(st.nextToken());
                    node.init(item, i + 2);
                } else {
                    node.init(-1, i + 2);
                }
                node.l = rt[d];
                rt[d] = pool[allo++];
            }
        }

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int query = Integer.parseInt(st.nextToken());
            int l0, r0, id;
            Node p = null, q = null;
            switch (query) {
            case 1:
                id = Integer.parseInt(st.nextToken());
                l0 = Integer.parseInt(st.nextToken());
                r0 = Integer.parseInt(st.nextToken());
                rt[id] = range(rt[id], l0, r0 + 1);
                rt[id].r.l.flip();
                break;

            case 2:
                id = Integer.parseInt(st.nextToken());
                l0 = Integer.parseInt(st.nextToken());
                r0 = Integer.parseInt(st.nextToken());
                int l1 = Integer.parseInt(st.nextToken());
                int r1 = Integer.parseInt(st.nextToken());
                if (r0 + 1 == l1) {
                    rt[id] = range(rt[id], l0, r0 + 1);
                    rt[id].r.l.flip();
                    rt[id] = range(rt[id], l1, r1 + 1);
                    rt[id].r.l.flip();
                    rt[id] = range(rt[id], l0, r1 + 1);
                    rt[id].r.l.flip();
                } else {
                    rt[id] = range(rt[id], l1, r1 + 1);
                    q = rt[id].r.l;
                    rt[id].r.l = nodeNull;
                    rt[id].r.mconcat();
                    rt[id].mconcat();
                    rt[id] = range(rt[id], l0, r0 + 1);
                    p = rt[id].r.l;
                    rt[id].r.l = q;
                    rt[id].r.mconcat();
                    rt[id].mconcat();
                    int s = l1 + (r1 - r0) - (l1 - l0);
                    rt[id] = range(rt[id], s, s);
                    rt[id].r.l = p;
                    rt[id].r.mconcat();
                    rt[id].mconcat();
                }
                break;

            case 3:
                l0 = Integer.parseInt(st.nextToken());
                r0 = Integer.parseInt(st.nextToken());

                rt[0] = range(rt[0], l0, r0 + 1);
                p = rt[0].r.l;
                rt[1] = range(rt[1], l0, r0 + 1);
                q = rt[1].r.l;
                rt[0].r.l = q;
                rt[0].r.mconcat();
                rt[0].mconcat();
                rt[1].r.l = p;
                rt[1].r.mconcat();
                rt[1].mconcat();
                break;

            case 4:
                l0 = Integer.parseInt(st.nextToken());
                r0 = Integer.parseInt(st.nextToken());

                ny = 0;
                rt[0] = range(rt[0], l0, r0 + 1);
                p = rt[0].r.l;
                inorder(p, 0);
                id = ny;
                for (int i = 0; i < id; i++) {
                    a[i].x = y[i];
                }
                ny = 0;
                rt[1] = range(rt[1], l0, r0 + 1);
                q = rt[1].r.l;
                inorder(q, 0);
                for (int i = 0; i < id; i++) {
                    a[i].y = y[i];
                }
                double result = smallestEnclosingCircle(id).r;
                bw.write(String.format("%.2f\n", result));
                break;

            default:
                break;
            }
        }

        bw.newLine();
        bw.close();
        br.close();
    }
}


Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
#define MAXN 200005
#define kt root->ch[1]->ch[0]
const int inf = 100000;
struct Node
{
    Node *ch[2],*pre;
    int sz,key,rev;
};
class Splay
{
public:
    void init()
    {
        cnt=0;
        top=0;
        nill=node;
        nill->sz=0;
        root=new_node(nill,-inf);
        root->ch[1]=new_node(root,-inf);
        up(root);
    }
    void insert(int pos,int num[],int l,int r)
    {
        Node *x=find_k(pos),*y=find_k(pos+1);
        splay(x,nill);
        splay(y,root);
        kt=make_tree(root->ch[1],num,l,r);
        up(root->ch[1]);
        up(root);
    }
    void reverse(int pos,int n)
    {
        Node *x=find_k(pos-1),*y=find_k(pos+n);
        splay(x,nill);
        splay(y,root);
        kt->rev^=1;
        up(root->ch[1]);
        up(root);
    }
    void cut(int pos1, int n1, int pos2, int n2) {
        Node *x = find_k(pos1 - 1), *y = find_k(pos1 + n1);
        splay(x, nill);
        splay(y, root);
        Node *c1 = kt;
        kt = nill;
        up(root->ch[1]);
        up(root);

        x = find_k(pos2 - n1 - 1);
        y = find_k(pos2 - n1 + n2);
        splay(x, nill);
        splay(y, root);
        Node *c2 = kt;
        kt = c1;
        c1->pre = root->ch[1];
        up(root->ch[1]);
        up(root);

        x = find_k(pos1 - 1);
        y = find_k(pos1);
        splay(x, nill);
        splay(y, root);
        kt = c2;
        c2->pre = root->ch[1];
        up(root->ch[1]);
        up(root);
    }
    void takeNum(int *a, int pos, int n) {
        Node *x = find_k(pos - 1), *y = find_k(pos + n);
        splay(x, nill);
        splay(y, root);
        int sz = 0;
        make_array(a, sz, kt);
    }
private:
    int cnt,top;
    Node node[MAXN],*mem[MAXN],*root,*nill,*stack[MAXN];
    void up(Node *x)
    {
        x->sz=1+x->ch[0]->sz+x->ch[1]->sz;
    }
    void down(Node *x)
    {
        if(x->rev)
        {
            x->rev=0;
            x->ch[0]->rev^=1;
            x->ch[1]->rev^=1;
            swap(x->ch[0],x->ch[1]);
        }
    }
    Node *new_node(Node *f,int v)//??????v?????f
    {
        Node *x;
        if(top) x=mem[--top];
        else x=&node[++cnt];
        x->key=v;
        x->sz=1;
        x->rev=0;
        x->pre=f;
        x->ch[0]=x->ch[1]=nill;
        return x;
    }
    void rotate(Node *x,int f)
    {
        Node *y=x->pre;
        //down(y);
       // down(x);
        y->ch[!f]=x->ch[f];
        x->ch[f]->pre=y;
        x->pre=y->pre;
        if(y->pre!=nill) y->pre->ch[y->pre->ch[1]==y]=x;
        x->ch[f]=y;
        y->pre=x;
        up(y);
    }
    void splay(Node *x,Node *to)//?x???to???
    {
        int tot=0;
        Node *tmp=x;
        while(true)
        {
            stack[tot++]=tmp;
            tmp=tmp->pre;
            if(tmp==nill) break;
        }
        for(int i=tot-1;i>=0;i--) down(stack[i]);
        while(x->pre!=to)
        {
            if(x->pre->pre==to) rotate(x,x->pre->ch[0]==x);
            else
            {
                Node *y=x->pre,*z=y->pre;
                int f=(z->ch[0]==y);
                if(y->ch[f]==x) rotate(x,!f),rotate(x,f);
                else rotate(y,f),rotate(x,f);
            }
        }
        up(x);
        if(to==nill) root=x;
    }
    Node *find_k(int k)//?????k???
    {
        Node *x=root;
        while(true)
        {
            down(x);
            if(x->ch[0]->sz==k) return x;
            if(x->ch[0]->sz>k) x=x->ch[0];
            else
            {
                k-=(1+x->ch[0]->sz);
                x=x->ch[1];
            }
        }
    }
    Node *make_tree(Node *f,int num[],int l,int r)
    {
        if(r<l) return nill;
        int mid=(l+r)/2;
        Node *x=new_node(f,num[mid]);
        x->ch[0]=make_tree(x,num,l,mid-1);
        x->ch[1]=make_tree(x,num,mid+1,r);
        up(x);
        return x;
    }
    void make_array(int *a, int &sz, Node *x) {
        if (x == nill) return;
        down(x);
        make_array(a, sz, x->ch[0]);
        a[sz ++] = x->key;
        make_array(a, sz, x->ch[1]);
    }
    void clear(Node *x)//????
    {
        if(x==nill) return;
        mem[top++]=x;
        clear(x->ch[0]);
        clear(x->ch[1]);
    }
};
Splay splay;
int num[MAXN],n,m;
int px[MAXN], py[MAXN];

const double EPS = 1e-8;

int sgn(double x)
{
    if (fabs(x)<=EPS) return 0;
    return x>0?1:-1;
}

struct point
{
    double x,y;
    point(): x(0),y(0) {}
    point(double a,double b): x(a),y(b) {}
    point operator + (const point &b) const
    {
        return point(x+b.x,y+b.y);
    }
    point operator - (const point &b) const
    {
        return point(x-b.x,y-b.y);
    }
    double operator * (const point &b) const
    {
        return x*b.y-y*b.x;
    }
    double dis(const point &b) const
    {
        return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
    }
};

struct hplane
{
    point s,t;
    point cross (const hplane &b) const
    {
        point p=b.t-s;
        double s1=(b.t-s)*(b.s-s);
        double s2=(b.s-t)*(b.t-t);
        return point((s.x*s2+t.x*s1)/(s2+s1),(s.y*s2+t.y*s1)/(s2+s1));
    }
};
point p[MAXN],cen;


double calCircle(int *px, int *py, int n) {
    for (int i = 0; i < n; i ++) {
        p[i].x = px[i];
        p[i].y = py[i];
    }
    srand(time(0));
    random_shuffle(p, p + n);
    cen = p[0];
    double r = 0;
    for (int i=1;i<n;i++)
        if (sgn(cen.dis(p[i])-r)>0)
        {
            cen=p[i]; r=0;
            for (int j=0;j<i;j++)
                if (sgn(cen.dis(p[j])-r)>0)
                {
                    cen=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0);
                    r=p[i].dis(p[j])/2.0;
                    for (int k=0;k<j;k++)
                        if (sgn(cen.dis(p[k])-r)>0)
                        {
                            hplane l1,l2;
                            l1.s=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0);
                            l1.t=l1.s+point(p[i].y-p[j].y,p[j].x-p[i].x);
                            l2.s=point((p[i].x+p[k].x)/2.0,(p[i].y+p[k].y)/2.0);
                            l2.t=l2.s+point(p[i].y-p[k].y,p[k].x-p[i].x);
                            cen=l1.cross(l2);
                            r=cen.dis(p[i]);
                        }
                }
        }
    return r;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    splay.init();
    for (int i = 1; i <= n * 2; i ++) {
        scanf("%d", num + i);
    }
    splay.insert(0, num, 1, n * 2);
    for (int i = 0; i < m; i ++) {
        int ope;
        scanf("%d", &ope);
        if (ope == 1) {
            int id, l, r;
            scanf("%d%d%d", &id, &l, &r);
            if (id == 0) {
                splay.reverse(l, r - l + 1);
            } else {
                splay.reverse(l + n, r - l + 1);
            }
        } else if (ope == 2) {
            int id, l1, r1, l2, r2;
            scanf("%d%d%d%d%d", &id, &l1, &r1, &l2, &r2);
            if (id == 0) {
                splay.cut(l1, r1 - l1 + 1, l2, r2 - l2 + 1);
            } else {
                splay.cut(l1 + n, r1 - l1 + 1, l2 + n, r2 - l2 + 1);
            }
        } else if (ope == 3) {
            int l, r;
            scanf("%d%d", &l, &r);
            splay.cut(l, r - l + 1, l + n, r - l + 1);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            splay.takeNum(px, l, r - l + 1);
            splay.takeNum(py, l + n, r - l + 1);
            printf("%.2f\n", calCircle(px, py, r - l + 1));
        }
    }
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct _ct_node{
int size;
int priority;
int value;
int reverse;
struct _ct_node *left,*right;
} ct_node;
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By);
double get_r(int x1,int y1,int x2,int y2,int x3,int y3);
int inside(int x,int y);
void sed(int idx,int r_size,int x1,int x2,
int x3,int y1,int y2,int y3);
double solve();
void tra(ct_node *root,int *A);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
void push(ct_node *root);
ct_node* reverse(int A,int B,ct_node *root);
void computeTree();
int get_size(ct_node *root);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,
int*left_b,int*right_b,int left_size, int right_size);
int P[100000],st[100000],T[100000],a[100000],
b[100000],h1[100000],h2[100000],N,NN;
double pi,CX,CY,R;
ct_node poll[200000],*root[2];

int main(){
int M,x,l1,l2,r1,r2,i;
ct_node *p1,*p2,*p3,*p4,*p5,*p6;
pi=atan(1)*4;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++){
scanf("%d",&poll[i].value);
poll[i].priority=P[i]=rand();
poll[i].reverse=0;
poll[i].left=poll[i].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[0]=&poll[i];
else
if(i<T[i])
poll[T[i]].left=&poll[i];
else
poll[T[i]].right=&poll[i];
get_size(root[0]);
for(i=0;i<N;i++){
scanf("%d",&poll[i+N].value);
poll[i+N].priority=P[i]=rand();
poll[i+N].reverse=0;
poll[i+N].left=poll[i+N].right=NULL;
}
computeTree();
for(i=0;i<N;i++)
if(T[i]==-1)
root[1]=&poll[i+N];
else
if(i<T[i])
poll[T[i]+N].left=&poll[i+N];
else
poll[T[i]+N].right=&poll[i+N];
get_size(root[1]);
while(M--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d%d",&x,&l1,&r1);
root[x]=reverse(l1-1,r1-1,root[x]);
break;
case 2:
scanf("%d%d%d%d%d",&x,&l1,&r1,&l2,&r2);
split(r2-1,&p4,&p5,root[x]);
split(l2-2,&p3,&p4,p4);
split(r1-1,&p2,&p3,p3);
split(l1-2,&p1,&p2,p2);
root[x]=merge(merge(p1,p4),merge(p3,merge(p2,p5)));
break;
case 3:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
root[0]=merge(merge(p1,p5),p3);
root[1]=merge(merge(p4,p2),p6);
break;
default:
scanf("%d%d",&l1,&r1);
split(r1-1,&p2,&p3,root[0]);
split(l1-2,&p1,&p2,p2);
split(r1-1,&p5,&p6,root[1]);
split(l1-2,&p4,&p5,p5);
NN=0;
tra(p2,a);
NN=0;
tra(p5,b);
root[0]=merge(merge(p1,p2),p3);
root[1]=merge(merge(p4,p5),p6);
printf("%.2lf\n",solve());
break;
}
}
return 0;
}
long long cross(long long Ox,long long Oy,
long long Ax,long long Ay,long long Bx,long long By){
return (Ax-Ox)*(By-Oy)-(Ay-Oy)*(Bx-Ox);
}
double get_r(int x1,int y1,int x2,
int y2,int x3,int y3){
int minx,maxx;
double s2,s3,mx2,my2,mx3,my3;
mx2=((double)(x2+x1))/2;
my2=((double)(y2+y1))/2;
mx3=((double)(x3+x1))/2;
my3=((double)(y3+y1))/2;
if(y1==y2 && y1==y3){
CY=y1;
minx=x1;
if(x2<minx)
minx=x2;
if(x3<minx)
minx=x3;
maxx=x1;
if(x2>maxx)
maxx=x2;
if(x3>maxx)
maxx=x3;
CX=((double)(minx+maxx))/2;
return ((double)(maxx-minx))/2;
}
if(y1==y2){
s3=(x1-x3)/(double)(y3-y1);
CX=mx2;
CY=s3*CX-s3*mx3+my3;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
if(y1==y3){
s2=(x1-x2)/(double)(y2-y1);
CX=mx3;
CY=s2*CX-s2*mx2+my2;
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
s2=(x1-x2)/(double)(y2-y1);
s3=(x1-x3)/(double)(y3-y1);
if(s2==s3)
return 0;
CX=(mx2*s2-mx3*s3-my2+my3)/(s2-s3);
CY=(my3*s2-my2*s3+s2*s3*mx2-s2*s3*mx3)/(s2-s3);
return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1));
}
int inside(int x,int y){
return sqrt((x-CX)*(x-CX)+(y-CY)*(y-CY))<=R;
}
void sed(int idx,int r_size,int x1,
int x2,int x3,int y1,int y2,int y3){
if(idx==NN || r_size==3){
if(r_size<=1){
R=0;
CX=x1;
CY=y1;
}
else if(r_size==2){
R=sqrt((x2-x1)*(double)(x2-x1)+(y2-y1)*(
    double)(y2-y1))/2;
CX=((double)(x1+x2))/2;
CY=((double)(y1+y2))/2;
}
else
R=get_r(x1,y1,x2,y2,x3,y3);
return;
}
sed(idx+1,r_size,x1,x2,x3,y1,y2,y3);
if(!inside(h1[idx],h2[idx]))
switch(r_size){
case 0:
sed(idx+1,r_size+1,h1[idx],x2,x3,h2[idx],y2,y3);
break;
case 1:
sed(idx+1,r_size+1,x1,h1[idx],x3,y1,h2[idx],y3);
break;
default:
sed(idx+1,r_size+1,x1,x2,h1[idx],y1,y2,h2[idx]);
}
return;
}
double solve(){
int n=NN,k=0,t,i,j;
sort_a2(a,b,NN);
for(i=0;i<n;i++){
while(k>=2 && cross(h1[k-2],h2[k-2],h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
for(i=n-2,t=k+1;i>=0;i--){
while(k>=t && cross(h1[k-2],h2[k-2],
h1[k-1],h2[k-1],a[i],b[i])<=0)
k--;
h1[k]=a[i];
h2[k++]=b[i];
}
k--;
if(k<=1)
return 0;
if(k==2)
return sqrt((h1[0]-h1[1])*(
double)(h1[0]-h1[1])+(h2[0]-h2[1])*
(double)(h2[0]-h2[1]))/2;
for(i=0;i<k;i++){
j=rand()%(k-i)+i;
t=h1[i];
h1[i]=h1[j];
h1[j]=t;
t=h2[i];
h2[i]=h2[j];
h2[j]=t;
}
NN=k;
sed(0,0,0,0,0,0,0,0);
return R;
}
void tra(ct_node *root,int *A){
if(!root)
return;
push(root);
tra(root->left,A);
A[NN++]=root->value;
tra(root->right,A);
return;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
L->right=merge(L->right,R);
recalc(L);
return L;
}
push(R);
R->left=merge(L,R->left);
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x){
split(x-curIndex-1,&t,R,root->right);
root->right=t;
recalc(root);
*L=root;
}
else{
split(x,L,&t,root->left);
root->left=t;
recalc(root);
*R=root;
}
return;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}
ct_node* reverse(int A,int B,ct_node *root){
ct_node *l,*m,*r;
split(A-1,&l,&r,root);
split(B-A,&m,&r,r);
m->reverse^=1;
return merge(merge(l,m),r);
}
void computeTree(){
int i,k,top=-1;
for(i=0;i<N;i++){
k=top;
while(k>=0 && P[st[k]]<P[i])
k--;
if(k!=-1)
T[i]=st[k];
if(k<top)
T[st[k+1]]=i;
st[++k]=i;
top=k;
}
T[st[0]]=-1;
return;
}
int get_size(ct_node *root){
if(!root)
return 0;
root->size=get_size(root->left)+get_size(root->right)+1;
return root->size;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,
int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i] < right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}


Post a Comment

0 Comments