板子们

数据结构

线段树

单点修改,区间和

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
comments powered by Disqus