Bookmarks

You haven't yet saved any bookmarks. To bookmark a post, just click .

  • 板子们

  • 数据结构

    线段树

    单点修改,区间和

    ll tree[maxn << 2];
    void build(int l, int r, int v) { memset(tree, v, sizeof(tree)); }
    void update(int root, int left, int right, int pos, int k) {
        if (pos < left || pos > right)
            return;
        if (left == right) {
            tree[root] += k;
            return;
        }
        int mid = (left + right) >> 1;
        update(lson, left, mid, pos, k);
        update(rson, mid + 1, right, pos, k);
        tree[root] = tree[lson] + tree[rson];
    }
    
    ll query(int root, int left, int right, int ql, int qr) {
        if (qr < left || ql > right)
            return 0;
        if (ql <= left && right <= qr)
            return tree[root];
        int mid = (left + right) >> 1;
        return query(lson, left, mid, ql, qr) + query(rson, mid + 1, right, ql, qr);
    }
    ll qu(int l, int r) { return query(1, 0, maxn, l, r); }
    void up(int p, int k) { update(1, 0, maxn, p, k); }
    

    树论

    支配树

    truct node {
        vector<int> e[maxn];
        inline void add(int u, int v) { e[u].push_back(v); }
    } a, b, c, d;
    
    int dfn[maxn], id[maxn], dfa[maxn], sdom[maxn], idom[maxn], fa[maxn],
        mindfn[maxn], cnt;
    
    void dfs(int u) {
        dfn[u] = ++cnt;
        id[cnt] = u;
        for (int i : a.e[u]) {
            if (dfn[i]) {
                continue;
            }
            dfa[i] = u;
            dfs(i);
        }
    }
    
    int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        int tmp = find(fa[x]);
        if (dfn[sdom[mindfn[fa[x]]]] < dfn[sdom[mindfn[x]]]) {
            mindfn[x] = mindfn[fa[x]];
        }
        return fa[x] = tmp;
    }
    
    void zp() {
        for (int i = cnt; i > 1; i--) {
            int u = id[i];
            for (int v : b.e[u]) {
                if (!dfn[v]) {
                    continue;
                }
                find(v);
                if (dfn[sdom[mindfn[v]]] < dfn[sdom[u]]) {
                    sdom[u] = sdom[mindfn[v]];
                }
            }
            c.add(sdom[u], u);
            fa[u] = dfa[u];
            u = fa[u];
            for (int v : c.e[u]) {
                find(v);
                sdom[mindfn[v]] == u ? idom[v] = u : idom[v] = mindfn[v];
            }
        }
        for (int i = 2; i <= cnt; i++) {
            int u = id[i];
            if (idom[u] != sdom[u]) {
                idom[u] = idom[idom[u]];
            }
        }
    }
    
    void zp_write(int n) {
        for (int i = 2; i <= n; i++) {
            d.add(idom[i], i);
        }
    }
    

    数学

    快速乘,快速幂

    ll qm(ll a, ll b, ll c) {
        long long ans = 0, res = a;
        while (b) {
            if (b & 1)
                ans = (ans + res) % c;
            res = (res + res) % c;
            b >>= 1;
        }
        return (ll)ans;
    }
    ll mul(ll a, ll b) { return (ll)(__int128(a) * b % MOD); }
    ll qp(ll a, ll b, ll c) {
        ll ans = 1, res = a;
        while (b) {
            if (b & 1)
                ans = qm(ans, res, c);
            res = qm(res, res, c);
            b >>= 1;
        }
        return ans;
    }
    

    素数

    //前置:快速乘,快速幂
    //保证long long内结果准确
    ll prime[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    bool Miller_Rabin(ll x) {
        ll i, j, k;
        ll s = 0, t = x - 1;
        if (x == 2)
            return true;
        if (x < 2 || !(x & 1))
            return false;
        while (!(t & 1)) {
            s++;
            t >>= 1;
        }
        for (i = 0; i < 6 && prime[i] < x; ++i) {
            ll a = prime[i];
            ll b = qp(a, t, x);
            for (j = 1; j <= s; ++j) {
                k = qm(b, b, x);
                if (k == 1 && b != 1 && b != x - 1)
                    return false;
                b = k;
            }
            if (b != 1)
                return false;
        }
        return true;
    }
    

    逆元

    ll modInverse(ll a, ll p) { return qp(a, p - 2ll, p); }
    

    计算几何

    极角排序

    struct Vector {
        int x, y;
    };
    Vector pp[maxn], vc[maxn];
    
    inline double dc(Vector a, Vector b) {
        return 1.0 * a.x * b.y - 1.0 * a.y * b.x;
    }
    
    inline int xs(Vector a) {
        if (a.x >= 0 && a.y > 0)
            return 1;
        if (a.x < 0 && a.y >= 0)
            return 2;
        if (a.x <= 0 && a.y < 0)
            return 3;
        if (a.x > 0 && a.y <= 0)
            return 4;
    }
    
    bool operator<(const Vector &a, const Vector &b) {
        Vector p1 = a;
        Vector p2 = b;
        int l1, l2;
        l1 = xs(p1);
        l2 = xs(p2);
        return l1 == l2 ? dc(a, b) > 0 ? 1 : 0 : l1 < l2;
    }
    

    2019.11.22集合

    const int maxn=100010;
    namespace Treap{
        int num;
        struct Node{
            int data,key,sz;
            int ls,rs;
            Node(){};
            Node(int data,int key,int sz,int ls=0,int rs=0):
                data(data),key(key),sz(sz),ls(ls),rs(rs){};
        }T[maxn];
        void pushup(int x){
            T[x].sz=T[T[x].ls].sz+T[T[x].rs].sz+1;
        }
        int newnode(int x){
            T[++num]=Node(x,rand(),1);
            return num;
        }
        int merge(int x,int y){
            if(!x||!y)return x+y;
            if(T[x].key<T[y].key){
                T[x].rs=merge(T[x].rs,y);
                pushup(x);
                return x;
            }
            else{
                T[y].ls=merge(x,T[y].ls);
                pushup(y);
                return y;
            }
        }
        void split(int now,int k,int &x,int &y){
            if(!now){x=y=0;return;}
            
            if(T[now].data<=k)x=now,split(T[now].rs,k,T[now].rs,y);
            else y=now,split(T[now].ls,k,x,T[now].ls);
            pushup(now);
        }
        int kth(int now,int k){
            while(1){
                if(k<=T[T[now].ls].sz)now=T[now].ls;
                else if(k==T[T[now].ls].sz+1)return now;
                else k-=T[T[now].ls].sz+1,now=T[now].rs;
            }
        }
    }
    using namespace Treap;
    
    namespace Treap_with_point{
        struct node{
            node *ch[2];
            int data,key,sz,flip;
            int siz(int x){
                if(ch[x]!=NULL)return ch[x]->sz;
                else return 0;
            }
            void pushdown(){
                if(flip){
                    flip=0;
                    swap(ch[0],ch[1]);
                    if(ch[0]!=NULL)ch[0]->flip^=1;
                    if(ch[1]!=NULL)ch[1]->flip^=1;
                }
            }
            void maintain(){sz=1+siz(0)+siz(1);}
        }*root;
        typedef pair<node*,node*> droot;
        node *merge(node *a,node *b){
            if(a==NULL)return b;
            if(b==NULL)return a;
            a->pushdown();b->pushdown();
            if(a->key<b->key){
                a->ch[1]=merge(a->ch[1],b);
                a->maintain();
                return a;
            }
            else{
                b->ch[0]=merge(a,b->ch[0]);
                b->maintain();
                return b;
            }
        }
        droot split(node *a,int k){
            if(a==NULL)return droot(NULL,NULL);
            droot ret;
            a->pushdown();
            if(a->siz(0)>=k){
                ret=split(a->ch[0],k);
                a->ch[0]=ret.second;
                a->maintain();
                ret.second=a;
            }
            else{
                ret=split(a->ch[1],k-a->siz(0)-1);
                a->ch[1]=ret.first;
                a->maintain();
                ret.first=a;
            }
            return ret;
        }
        void insert(int x){
            node *t=new node;
            t->data=x;t->key=rand();t->sz=1;
            t->flip=0;t->ch[0]=t->ch[1]=NULL;
            root=merge(root,t);
        }
        void output(node *o){
            if(!o)return;
            o->pushdown();
            if(o->ch[0])output(o->ch[0]);
            printf("%d ",o->data);
            if(o->ch[1])output(o->ch[1]);
        }
    }
    //the Treap without Rotating,written by ndqzhang1111
    
    
    typedef long long ll;
    bool vis[MAXN];
    //int prime[MAXN];
    vector<int> prime;
    int tot;
    
    void get_prime() {
        //int tot = 0;
        for (int i = 2; i < MAXN; ++i) {
            if (!vis[i])
                prime.push_back(i);//prime[tot++] = i;
            for (int j = 0; j < prime.size(); ++j) {
                int d = i * prime[j];
                if (d >= MAXN)
                    break;
                vis[d] = true;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    //rewrite by KI_aq&ndqzhang1111
    
    typedef long long ll;
    //typedef int ll;
    const int maxn = 4e6 + 10, mod = 1e9 + 7;
    //First Step
    namespace Seive {
    vector<int> p;
    bool np[maxn];
    int cnt;
    void seive() {
      np[1] = 0;
      for (int i = 2, d; i < maxn; ++i) {
        if (!np[i]) {
          p.push_back(i);
        }
        for (auto v : p) {
          if ((d = i * v) >= maxn) {
            break;
          }
          np[d] = 1;
          if (i % v == 0) break;
        }
      }
      cnt = p.size();
    }
    }
    namespace Useless_Min25 {
    using namespace Seive;
    const int M = maxn;
    ll N;
    ll id1[M], id2[M];
    
    ll id(ll n) {
      if (n < M)return id1[n];
      else return id2[N / n];
    }
    ll mul(ll a, ll b) {
      return a * b % mod;
    }
    //f(p^k)=p^2k-p^k
    ll f(ll p) {
      if (p == 1)return 1;
      else return (mul(p, p) - p + mod) % mod;
    }
    //f(p) should be a poly...;
    
    vector<int> p;
    ll w[2 * M];
    ll m;
    ll g1[2 * M], g2[2 * M], gp1[M], gp2[M];
    ll g(int p) {return (g2[p] - g1[p] + mod) % mod;}//Sum_of [n/i]
    ll h(int y) {return (gp2[y] - gp1[y] + mod) % mod;}//Sum_of [p[i]]
    //calc_in_O(1)
    void init_g() {
      gp1[0] = 2; gp2[0] = 4;
      for (int i = 1; i < p.size(); ++i) {
        gp1[i] = (gp1[i - 1] + p[i]) % mod;
        gp2[i] = (mul(p[i], p[i]) + gp2[i - 1]) % mod;
      }
      for (ll i = 1; i <= N; i = N / (N / i) + 1) {
        w[++m] = N / i;
        if (w[m] < M)id1[w[m]] = m;
        else id2[N / w[m]] = m;
        //sumh(n,p[i]);
        g1[m] = w[m] % mod;
        g2[m] = (mul(mul(mul(g1[m], g1[m] + 1), g1[m] * 2 + 1), 166666668) - 1) % mod;
        g1[m] = (mul(mul(g1[m], (g1[m] + 1)), 500000004) - 1) % mod;
      }
      ////j from 1->|P| calc g(n,j)
      //g(n,j)=g(n,j-1)-f(pj)*(g(n/p[j],j-1)-g(p[j],j-1))
      for (int i = 0; i < p.size(); ++i) {
        ll sqr_pi = 1ll * p[i] * p[i];
        for (int j = 1; j <= m && sqr_pi <= w[j]; ++j) {
          ll y = id(w[j] / p[i]);
          g1[j] = (g1[j] - mul(p[i], (g1[y] - (i - 1 >= 0 ? gp1[i - 1] : 0) + mod)) + mod) % mod;
          g2[j] = (g2[j] - mul(mul(p[i], p[i]), (g2[y] - (i - 1 >= 0 ? gp2[i - 1] : 0) + mod)) + mod) % mod;
        }
      }
    }
    int tim;
    ll S(ll x, int y) {
      if (x <= 1 || (y >= 0 && p[y] > x))return 0;
      int k = id(x);
      //ans = g(n,|p|) - sumf(n,p[i])
      ll ret = (g(k) - h(y) + mod) % mod;
      //+F*(pe)*(s...+(e>1))
      for (int i = y + 1; i < cnt && 1ll * p[i]*p[i] <= x; ++i) {
        ll pe = p[i];
        for (int e = 1; pe <= x; ++e, pe = 1ll * pe * p[i] ) {
          ret = (  1ll * ret + 1ll * f(pe % mod) * (S(x / pe, i) + (e != 1)) % mod) % mod;
        }
      }
      return ret;
    }
    
    ll sum(ll n) {
      N = n; m = 0;
      init_g();
      return (S(N, -1) + f(1)) % mod;
    }
    ll Query(ll l, ll r) {
      return (sum(r) - sum(l - 1) + mod) % mod;
    }
    }//Written by KI_aq
    
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <string>
    #include <vector>
    using namespace std;
    
    struct Point {
        double x, y, z;
    } p[105];
    
    double dist(Point a, Point b) {
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
                    (a.z - b.z) * (a.z - b.z));
    }
    
    double ac(int n) {
        double ans = 1e9;
        Point tmp;
        tmp.x = tmp.y = tmp.z = 0;
        ;
        int s = 1;
        double step = 1000;
        double esp = 0.0000001;
        while (step > esp) {
            for (int i = 1; i <= n; i++) {
                if (dist(tmp, p[s]) < dist(tmp, p[i]))
                    s = i;
            }
            double Dist = dist(tmp, p[s]);
            ans = min(ans, Dist);
            tmp.x += (p[s].x - tmp.x) / Dist * step;
            tmp.y += (p[s].y - tmp.y) / Dist * step;
            tmp.z += (p[s].z - tmp.z) / Dist * step;
            step *= 0.999;
        }
        return ans;
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z);
        }
        double ans = ac(n);
        printf("%.5f\n", ans);
    }//minimal ball cover by lucas
    
    ll tree[maxn << 2];
    void build(int l, int r, int v) { memset(tree, v, sizeof(tree)); }
    void update(int root, int left, int right, int pos, int k) {
        if (pos < left || pos > right)
            return;
        if (left == right) {
            tree[root] += k;
            return;
        }
        int mid = (left + right) >> 1;
        update(lson, left, mid, pos, k);
        update(rson, mid + 1, right, pos, k);
        tree[root] = tree[lson] + tree[rson];
    }
    
    ll query(int root, int left, int right, int ql, int qr) {
        if (qr < left || ql > right)
            return 0;
        if (ql <= left && right <= qr)
            return tree[root];
        int mid = (left + right) >> 1;
        return query(lson, left, mid, ql, qr) + query(rson, mid + 1, right, ql, qr);
    }
    ll qu(int l, int r) { return query(1, 0, maxn, l, r); }
    void up(int p, int k) { update(1, 0, maxn, p, k); }
    //segtree lucas
    
    struct node {
        vector<int> e[maxn];
        inline void add(int u, int v) { e[u].push_back(v); }
    } a, b, c, d;
    
    int dfn[maxn], id[maxn], dfa[maxn], sdom[maxn], idom[maxn], fa[maxn],
        mindfn[maxn], cnt;
    
    void dfs(int u) {
        dfn[u] = ++cnt;
        id[cnt] = u;
        for (int i : a.e[u]) {
            if (dfn[i]) {
                continue;
            }
            dfa[i] = u;
            dfs(i);
        }
    }
    
    int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        int tmp = find(fa[x]);
        if (dfn[sdom[mindfn[fa[x]]]] < dfn[sdom[mindfn[x]]]) {
            mindfn[x] = mindfn[fa[x]];
        }
        return fa[x] = tmp;
    }
    
    void zp() {
        for (int i = cnt; i > 1; i--) {
            int u = id[i];
            for (int v : b.e[u]) {
                if (!dfn[v]) {
                    continue;
                }
                find(v);
                if (dfn[sdom[mindfn[v]]] < dfn[sdom[u]]) {
                    sdom[u] = sdom[mindfn[v]];
                }
            }
            c.add(sdom[u], u);
            fa[u] = dfa[u];
            u = fa[u];
            for (int v : c.e[u]) {
                find(v);
                sdom[mindfn[v]] == u ? idom[v] = u : idom[v] = mindfn[v];
            }
        }
        for (int i = 2; i <= cnt; i++) {
            int u = id[i];
            if (idom[u] != sdom[u]) {
                idom[u] = idom[idom[u]];
            }
        }
    }
    
    void zp_write(int n) {
        for (int i = 2; i <= n; i++) {
            d.add(idom[i], i);
        }
    }//zp tree
    
    ll qm(ll a, ll b, ll c) {
        long long ans = 0, res = a;
        while (b) {
            if (b & 1)
                ans = (ans + res) % c;
            res = (res + res) % c;
            b >>= 1;
        }
        return (ll)ans;
    }
    ll mul(ll a, ll b) { return (ll)(__int128(a) * b % MOD); }
    ll qp(ll a, ll b, ll c) {
        ll ans = 1, res = a;
        while (b) {
            if (b & 1)
                ans = qm(ans, res, c);
            res = qm(res, res, c);
            b >>= 1;
        }
        return ans;
    }
    
    //前置:快速乘,快速幂
    //保证long long内结果准确
    ll prime[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    bool Miller_Rabin(ll x) {
        ll i, j, k;
        ll s = 0, t = x - 1;
        if (x == 2)
            return true;
        if (x < 2 || !(x & 1))
            return false;
        while (!(t & 1)) {
            s++;
            t >>= 1;
        }
        for (i = 0; i < 6 && prime[i] < x; ++i) {
            ll a = prime[i];
            ll b = qp(a, t, x);
            for (j = 1; j <= s; ++j) {
                k = qm(b, b, x);
                if (k == 1 && b != 1 && b != x - 1)
                    return false;
                b = k;
            }
            if (b != 1)
                return false;
        }
        return true;
    }
    
    ll modInverse(ll a, ll p) { return qp(a, p - 2ll, p); }
    
    struct Vector {
        int x, y;
    };
    Vector pp[maxn], vc[maxn];
    
    inline double dc(Vector a, Vector b) {
        return 1.0 * a.x * b.y - 1.0 * a.y * b.x;
    }
    
    inline int xs(Vector a) {
        if (a.x >= 0 && a.y > 0)
            return 1;
        if (a.x < 0 && a.y >= 0)
            return 2;
        if (a.x <= 0 && a.y < 0)
            return 3;
        if (a.x > 0 && a.y <= 0)
            return 4;
    }
    
    bool operator<(const Vector &a, const Vector &b) {
        Vector p1 = a;
        Vector p2 = b;
        int l1, l2;
        l1 = xs(p1);
        l2 = xs(p2);
        return l1 == l2 ? dc(a, b) > 0 ? 1 : 0 : l1 < l2;
    }//极角排序
    
    const int INF = 0x7fffffff;
    const int maxn = 1e5 + 50;
    const double INFF = 1.0 * 1e18;
    struct MEdge {
        int from, to, cap;
        double cost;
        MEdge(int from, int to, int cap, double cost)
            : from(from), to(to), cap(cap), cost(cost) {}
    };
    
    struct MCMF { // qdd tql
        int n, s, t, flow;
        double cost;
        vector<MEdge> es;
        vector<vector<int>> G;
        vector<double> d;
        vector<int> p, a; // dis, prev, add
        deque<bool> in;
    
        MCMF(int n, int s, int t)
            : n(n), s(s), t(t), flow(0), cost(0.0), G(n + 1), p(n + 1), a(n + 1) {}
    
        void add_edge(int u, int v, int cap, double cost) {
            G[u].push_back(es.size());
            es.emplace_back(u, v, cap, cost);
            G[v].push_back(es.size());
            es.emplace_back(v, u, 0, -cost);
        }
    
        bool spfa() {
            d.assign(n + 1, INFF);
            in.assign(n + 1, false);
            d[s] = 0;
            in[s] = 1;
            a[s] = INF;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                in[u] = false;
                for (int &i : G[u]) {
                    MEdge &e = es[i];
                    if (e.cap && d[e.to] > d[u] + e.cost) {
                        d[e.to] = d[u] + e.cost;
                        p[e.to] = i;
                        a[e.to] = min(a[u], e.cap);
                        if (!in[e.to]) {
                            q.push(e.to);
                            in[e.to] = true;
                        }
                    }
                }
            }
            return d[t] != INFF;
        }
    
        void solve() {
            while (spfa()) {
                flow += a[t];
                cost += a[t] * d[t];
                int u = t;
                while (u != s) {
                    es[p[u]].cap -= a[t];
                    es[p[u] ^ 1].cap += a[t];
                    u = es[p[u]].from;
                }
            }
        }
    };//dinic