Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
- // #pragma comment(linker, "/stack:200000000"]
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- #include <set>
- #include <map>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <stack>
- #include <random>
- #include <fstream>
- #include <sstream>
- #include <chrono>
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define ld long double
- #define hm unordered_map
- #define pii pair<int, int>
- #define sz(a) (int)a.size()
- #define all(a) a.begin(), a.end()
- #define cinv(v) for (auto& x: v) cin >> x
- #define fr(i, n) for (int i = 0; i < n; ++i)
- #define fl(i, l, n) for (int i = l; i < n; ++i)
- #define int ll
- using namespace std;
- #ifdef __LOCAL
- #define dbg(x) cerr << #x << " : " << x << '\n'
- const int maxn = 20;
- #else
- #define dbg(x)
- const int maxn = 2e5 + 20;
- #endif
- //tg: @galebickosikasa
- const ll inf = (ll) 4e18;
- const ld pi = asin (1) * 2;
- const ld eps = 1e-6;
- const ll mod = (ll)1e9 + 7;
- const ll ns = 97;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- bool eq(ld a, ld b){
- return fabs(a - b) < eps;
- }
- struct Vector{
- ld x, y;
- Vector(ld _x = 0, ld _y = 0){
- x = _x, y = _y;
- }
- Vector(Vector a, Vector b){
- *this = b - a;
- }
- ld len(){
- return sqrt(*this * *this);
- }
- void normalize(){
- *this = *this / len();
- }
- Vector rotate_ccw(){
- return Vector(-y, x);
- }
- Vector anti_rotate_ccw(){
- return Vector(y, -x);
- }
- Vector operator + (Vector other){
- return Vector(x + other.x, y + other.y);
- }
- Vector operator - (){
- return Vector(-x, -y);
- }
- Vector operator - (Vector other){
- return *this + -other;
- }
- Vector operator * (ld lambda){
- return Vector(x * lambda, y * lambda);
- }
- Vector operator / (ld lambda){
- return Vector(x / lambda, y / lambda);
- }
- ld operator ^ (Vector other){
- return x * other.y - other.x * y;
- }
- ld operator * (Vector other){
- return x * other.x + y * other.y;
- }
- bool operator == (const Vector other) const{
- return eq(x, other.x) && eq(y, other.y);
- }
- };
- struct Line{
- ld a, b, c;
- Line (Vector p, Vector q){
- Vector pq(p, q);
- Vector n = pq.rotate_ccw();
- a = -n.x, b = -n.y, c = p * n;
- }
- Line (ld _a = 1, ld _b = 1, ld _c = 0){
- a = _a, b = _b, c = _c;
- }
- Vector n(){
- return Vector(a, b);
- }
- bool parallel(const Line other) const {
- return eq(a * other.b, other.a * b);
- }
- pair<int, Vector> intersect(Line other){
- if (*this == other){
- return {2, Vector()};
- } if (parallel(other)){
- return {0, Vector()};
- }
- Vector t;
- t.x = (other.c * b - c * other.b) / (n() ^ other.n());
- t.y = -(other.c * a - c * other.a) / (n() ^ other.n());
- return {1, t};
- }
- bool operator == (const Line& other) const{
- return parallel(other) && other.belongs(random_point());
- }
- Vector random_point() const {
- Vector t;
- t.x = -(a * c) / (a * a + b * b), t.y = -(b * c) / (a * a + b * b);
- return t;
- }
- bool belongs(const Vector v) const {
- return eq(a * v.x + b * v.y + c, 0);
- }
- Vector projection(Vector p){
- Vector z = n();
- Line tmp(p, p + z);
- pair<int, Vector> q = intersect(tmp);
- return q.second;
- }
- }; // s = v + g / 2 - 1
- ll gcd(ll a, ll b){
- if (b == 0){
- return a;
- }
- return gcd(b, a % b);
- }
- bool is_on(Vector a, Vector b, Vector k){
- return eq(Vector(a, k) ^ Vector(a, b), 0) && (Vector(a, k) * Vector(a, b) > 0 || eq(Vector(a, k) * Vector(a, b), 0)) && (Vector(b, k) * Vector(b, a) > 0 || eq(Vector(b, k) * Vector(b, a), 0));
- }
- struct Polygon{
- vector<Vector> vertices;
- ll doubled_area(){
- ll ans = 0;
- vertices.pb(vertices.front());
- for (int i = 0; i < vertices.size() - 1; ++i){
- ans += (ll)(vertices[i] ^ vertices[i + 1]);
- }
- vertices.pop_back();
- return fabs(ans);
- }
- ld area(){
- return doubled_area() / 2.0;
- }
- ll count_of_point(){
- auto s = doubled_area();
- ll cnt = 0;
- vertices.pb(vertices.front());
- for (int i = 0; i < vertices.size() - 1; ++i){
- int x = gcd(abs((ll)vertices[i].x - (ll)vertices[i + 1].x), abs((ll)vertices[i].y - (ll)vertices[i + 1].y));
- cerr << x << '\n';
- cnt += x;
- }
- vertices.pop_back();
- ll v = (s - cnt + 2) / 2;
- return v;
- }
- };
- struct Circle{
- Vector o;
- ld r;
- Circle (Vector A, Vector B, Vector C){
- Vector a(B, C);
- Vector b(A, C);
- a = a / 2, b = b / 2;
- Vector m = B + a, n = A + b;
- Line tmp1(m, m + a.rotate_ccw());
- Line tmp2(n, n + b.rotate_ccw());
- auto t = tmp1.intersect(tmp2);
- o = t.second;
- r = Vector(o, A).len();
- }
- Circle (Vector A, Vector B) {
- Vector C (A, B);
- C = C / 2.0;
- o = A + C;
- r = C.len ();
- }
- Circle (Vector _o = Vector(), ld _r = 1){
- o = _o;
- r = _r;
- }
- pair<int, pair<Vector, Vector>> intersect(Line l){
- Vector h = l.projection(o);
- Vector oh(o, h);
- if (oh.len() > r){
- return {0, {Vector(), Vector()}};
- } else if (eq(oh.len(), r)){
- return {1, {h, Vector()}};
- } else{
- double ah = sqrt(r * r - oh * oh);
- Vector a = l.n();
- a = a.rotate_ccw();
- a.normalize();
- a = a * ah;
- Vector tmp1 = h + a;
- Vector tmp2 = h - a;
- return {2, {tmp1, tmp2}};
- }
- }
- pair<int, pair<Vector, Vector>> intersect(Circle other){
- if (o == other.o && !eq(r, other.r)){
- return {0, {Vector(), Vector()}};
- }
- Line l(2 * other.o.x - 2 * o.x, 2 * other.o.y - 2 * o.y, o.x * o.x - other.o.x * other.o.x + o.y * o.y - other.o.y * other.o.y - r * r + other.r * other.r);
- return intersect(l);
- }
- pair<int, pair<Vector, Vector>> tangent(Vector p){
- if (Vector(p, o).len() < r){
- return {0, {Vector(), Vector()}};
- }
- Vector t(o, p);
- ld dist = sqrt(t * t - r * r);
- Circle tmp(p, dist);
- return intersect(tmp);
- }
- bool operator == (const Circle& other) const{
- return o == other.o && eq(r, other.r);
- }
- ld leght_of_part(ld corner){
- return r * corner;
- }
- bool is_on(Vector v){
- return eq(Vector(o, v).len(), r);
- }
- bool is_in (Vector v) {
- return is_on (v) || Vector (o, v).len () < r;
- }
- };
- Circle kek2 (vector<Vector>& goo, Vector a, Vector b) {
- Circle C (a, b);
- fr (i, sz (goo)) {
- if (!C.is_in (goo[i])) C = Circle (goo[i], a, b);
- }
- return C;
- }
- Circle kek1 (vector<Vector>& goo, Vector v) {
- vector<int> t;
- fr (i, sz (goo)) t.pb (i);
- shuffle (all (t), rnd);
- //shuffle (all (goo), rnd ());
- //for (auto& x: t) dbg (x);
- //dbg (sz (goo));
- Circle C (goo[t[0]], v);
- vector<Vector> tmp = {goo[t[0]]};
- fl (i, 1, sz (goo)) {
- if (C.is_in (goo[t[i]])) {}
- else C = kek2 (tmp, goo[t[i]], v);
- tmp.pb (goo[t[i]]);
- }
- return C;
- }
- Circle kek (vector<Vector>& goo) {
- vector<int> t;
- fr (i, sz (goo)) t.pb (i);
- shuffle (all (t), rnd);
- //shuffle (all (goo), rnd ());
- Circle C (goo[t[0]], goo[t[1]]);
- //for (auto& x: t) cerr << x << '\n';
- vector<Vector> tmp = {goo[t[0]], goo[t[1]]};
- fl (i, 2, sz (goo)) {
- if (C.is_in (goo[t[i]])) {}
- else C = kek1 (tmp, goo[t[i]]);
- tmp.pb (goo[t[i]]);
- }
- return C;
- }
- signed main () {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cout.precision (15);
- cout << fixed;
- int n;
- cin >> n;
- vector<Vector> goo;
- fr (i, n) {
- ld x, y, r;
- cin >> x >> y >> r;
- for (ld alpha = 0; alpha <= 2 * pi; alpha += pi / 20000.0) {
- goo.pb ({x + r * cos (alpha), y + r * sin (alpha)});
- }
- }
- auto C = kek (goo);
- cout << C.r;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement