数据结构
线段树
单点修改，区间和
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