Advertisement
Galebickosikasa

Untitled

May 19th, 2020
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.46 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. #define int ll
  36.  
  37. using namespace std;
  38.  
  39.  
  40. #ifdef __LOCAL
  41. #define dbg(x) cerr << #x << " : " << x << '\n'
  42. const int maxn = 20;
  43. #else
  44. #define dbg(x)
  45. const int maxn = 2e5 + 20;
  46. #endif
  47.  
  48. //tg: @galebickosikasa
  49.  
  50. const ll inf = (ll) 4e18;
  51. const ld pi = asin (1) * 2;
  52. const ld eps = 1e-6;
  53. const ll mod = (ll)1e9 + 7;
  54. const ll ns = 97;
  55.  
  56. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  57.  
  58. bool eq(ld a, ld b){
  59. return fabs(a - b) < eps;
  60. }
  61.  
  62. struct Vector{
  63. ld x, y;
  64.  
  65. Vector(ld _x = 0, ld _y = 0){
  66. x = _x, y = _y;
  67. }
  68.  
  69. Vector(Vector a, Vector b){
  70. *this = b - a;
  71. }
  72.  
  73. ld len(){
  74. return sqrt(*this * *this);
  75. }
  76.  
  77. void normalize(){
  78. *this = *this / len();
  79. }
  80.  
  81. Vector rotate_ccw(){
  82. return Vector(-y, x);
  83. }
  84.  
  85. Vector anti_rotate_ccw(){
  86. return Vector(y, -x);
  87. }
  88.  
  89. Vector operator + (Vector other){
  90. return Vector(x + other.x, y + other.y);
  91. }
  92.  
  93. Vector operator - (){
  94. return Vector(-x, -y);
  95. }
  96.  
  97. Vector operator - (Vector other){
  98. return *this + -other;
  99. }
  100.  
  101. Vector operator * (ld lambda){
  102. return Vector(x * lambda, y * lambda);
  103. }
  104.  
  105. Vector operator / (ld lambda){
  106. return Vector(x / lambda, y / lambda);
  107. }
  108.  
  109. ld operator ^ (Vector other){
  110. return x * other.y - other.x * y;
  111. }
  112.  
  113. ld operator * (Vector other){
  114. return x * other.x + y * other.y;
  115. }
  116.  
  117. bool operator == (const Vector other) const{
  118. return eq(x, other.x) && eq(y, other.y);
  119. }
  120.  
  121. };
  122.  
  123. struct Line{
  124. ld a, b, c;
  125.  
  126. Line (Vector p, Vector q){
  127. Vector pq(p, q);
  128. Vector n = pq.rotate_ccw();
  129. a = -n.x, b = -n.y, c = p * n;
  130. }
  131.  
  132. Line (ld _a = 1, ld _b = 1, ld _c = 0){
  133. a = _a, b = _b, c = _c;
  134. }
  135.  
  136. Vector n(){
  137. return Vector(a, b);
  138. }
  139.  
  140. bool parallel(const Line other) const {
  141. return eq(a * other.b, other.a * b);
  142. }
  143.  
  144. pair<int, Vector> intersect(Line other){
  145. if (*this == other){
  146. return {2, Vector()};
  147. } if (parallel(other)){
  148. return {0, Vector()};
  149. }
  150. Vector t;
  151. t.x = (other.c * b - c * other.b) / (n() ^ other.n());
  152. t.y = -(other.c * a - c * other.a) / (n() ^ other.n());
  153. return {1, t};
  154. }
  155.  
  156. bool operator == (const Line& other) const{
  157. return parallel(other) && other.belongs(random_point());
  158. }
  159.  
  160. Vector random_point() const {
  161. Vector t;
  162. t.x = -(a * c) / (a * a + b * b), t.y = -(b * c) / (a * a + b * b);
  163. return t;
  164. }
  165.  
  166. bool belongs(const Vector v) const {
  167. return eq(a * v.x + b * v.y + c, 0);
  168. }
  169.  
  170. Vector projection(Vector p){
  171. Vector z = n();
  172. Line tmp(p, p + z);
  173. pair<int, Vector> q = intersect(tmp);
  174. return q.second;
  175. }
  176.  
  177. }; // s = v + g / 2 - 1
  178.  
  179. ll gcd(ll a, ll b){
  180. if (b == 0){
  181. return a;
  182. }
  183. return gcd(b, a % b);
  184. }
  185.  
  186. bool is_on(Vector a, Vector b, Vector k){
  187. 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));
  188. }
  189.  
  190. struct Polygon{
  191. vector<Vector> vertices;
  192.  
  193. ll doubled_area(){
  194. ll ans = 0;
  195. vertices.pb(vertices.front());
  196. for (int i = 0; i < vertices.size() - 1; ++i){
  197. ans += (ll)(vertices[i] ^ vertices[i + 1]);
  198. }
  199. vertices.pop_back();
  200. return fabs(ans);
  201. }
  202. ld area(){
  203. return doubled_area() / 2.0;
  204. }
  205.  
  206. ll count_of_point(){
  207. auto s = doubled_area();
  208. ll cnt = 0;
  209. vertices.pb(vertices.front());
  210. for (int i = 0; i < vertices.size() - 1; ++i){
  211. int x = gcd(abs((ll)vertices[i].x - (ll)vertices[i + 1].x), abs((ll)vertices[i].y - (ll)vertices[i + 1].y));
  212. cerr << x << '\n';
  213. cnt += x;
  214. }
  215. vertices.pop_back();
  216. ll v = (s - cnt + 2) / 2;
  217. return v;
  218. }
  219.  
  220. };
  221.  
  222. struct Circle{
  223. Vector o;
  224. ld r;
  225.  
  226. Circle (Vector A, Vector B, Vector C){
  227. Vector a(B, C);
  228. Vector b(A, C);
  229. a = a / 2, b = b / 2;
  230. Vector m = B + a, n = A + b;
  231. Line tmp1(m, m + a.rotate_ccw());
  232. Line tmp2(n, n + b.rotate_ccw());
  233. auto t = tmp1.intersect(tmp2);
  234. o = t.second;
  235. r = Vector(o, A).len();
  236. }
  237.  
  238. Circle (Vector A, Vector B) {
  239. Vector C (A, B);
  240. C = C / 2.0;
  241. o = A + C;
  242. r = C.len ();
  243. }
  244.  
  245. Circle (Vector _o = Vector(), ld _r = 1){
  246. o = _o;
  247. r = _r;
  248. }
  249.  
  250. pair<int, pair<Vector, Vector>> intersect(Line l){
  251. Vector h = l.projection(o);
  252. Vector oh(o, h);
  253. if (oh.len() > r){
  254. return {0, {Vector(), Vector()}};
  255. } else if (eq(oh.len(), r)){
  256. return {1, {h, Vector()}};
  257. } else{
  258. double ah = sqrt(r * r - oh * oh);
  259. Vector a = l.n();
  260. a = a.rotate_ccw();
  261. a.normalize();
  262. a = a * ah;
  263. Vector tmp1 = h + a;
  264. Vector tmp2 = h - a;
  265. return {2, {tmp1, tmp2}};
  266. }
  267. }
  268.  
  269. pair<int, pair<Vector, Vector>> intersect(Circle other){
  270. if (o == other.o && !eq(r, other.r)){
  271. return {0, {Vector(), Vector()}};
  272. }
  273. 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);
  274. return intersect(l);
  275. }
  276.  
  277. pair<int, pair<Vector, Vector>> tangent(Vector p){
  278. if (Vector(p, o).len() < r){
  279. return {0, {Vector(), Vector()}};
  280. }
  281. Vector t(o, p);
  282. ld dist = sqrt(t * t - r * r);
  283. Circle tmp(p, dist);
  284. return intersect(tmp);
  285. }
  286.  
  287. bool operator == (const Circle& other) const{
  288. return o == other.o && eq(r, other.r);
  289. }
  290.  
  291. ld leght_of_part(ld corner){
  292. return r * corner;
  293. }
  294.  
  295. bool is_on(Vector v){
  296. return eq(Vector(o, v).len(), r);
  297. }
  298.  
  299. bool is_in (Vector v) {
  300. return is_on (v) || Vector (o, v).len () < r;
  301. }
  302.  
  303. };
  304.  
  305. Circle kek2 (vector<Vector>& goo, Vector a, Vector b) {
  306. Circle C (a, b);
  307. fr (i, sz (goo)) {
  308. if (!C.is_in (goo[i])) C = Circle (goo[i], a, b);
  309. }
  310. return C;
  311. }
  312.  
  313. Circle kek1 (vector<Vector>& goo, Vector v) {
  314. vector<int> t;
  315. fr (i, sz (goo)) t.pb (i);
  316. shuffle (all (t), rnd);
  317. //shuffle (all (goo), rnd ());
  318. //for (auto& x: t) dbg (x);
  319. //dbg (sz (goo));
  320. Circle C (goo[t[0]], v);
  321. vector<Vector> tmp = {goo[t[0]]};
  322. fl (i, 1, sz (goo)) {
  323. if (C.is_in (goo[t[i]])) {}
  324. else C = kek2 (tmp, goo[t[i]], v);
  325. tmp.pb (goo[t[i]]);
  326. }
  327. return C;
  328. }
  329.  
  330. Circle kek (vector<Vector>& goo) {
  331. vector<int> t;
  332. fr (i, sz (goo)) t.pb (i);
  333. shuffle (all (t), rnd);
  334. //shuffle (all (goo), rnd ());
  335. Circle C (goo[t[0]], goo[t[1]]);
  336. //for (auto& x: t) cerr << x << '\n';
  337. vector<Vector> tmp = {goo[t[0]], goo[t[1]]};
  338. fl (i, 2, sz (goo)) {
  339. if (C.is_in (goo[t[i]])) {}
  340. else C = kek1 (tmp, goo[t[i]]);
  341. tmp.pb (goo[t[i]]);
  342. }
  343. return C;
  344. }
  345.  
  346. signed main () {
  347. ios_base::sync_with_stdio(false);
  348. cin.tie(nullptr);
  349. cout.tie(nullptr);
  350. cout.precision (15);
  351. cout << fixed;
  352. int n;
  353. cin >> n;
  354. vector<Vector> goo;
  355. fr (i, n) {
  356. ld x, y, r;
  357. cin >> x >> y >> r;
  358. for (ld alpha = 0; alpha <= 2 * pi; alpha += pi / 20000.0) {
  359. goo.pb ({x + r * cos (alpha), y + r * sin (alpha)});
  360. }
  361. }
  362. auto C = kek (goo);
  363. cout << C.r;
  364.  
  365.  
  366.  
  367.  
  368.  
  369. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement