Advertisement
prog3r

Untitled

Nov 8th, 2024
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.14 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vbo = vector<bool>;
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using pll = pair<ll, ll>;
  7. using ld = long double;
  8. using qll = queue<ll>;
  9. using vll = vector<ll>;
  10. using vvll = vector<vector<ll>>;
  11. using qld = queue<ld>;
  12. using vld = vector<ld>;
  13. using qpll = queue<pll>;
  14. using vpll = vector<pll>;
  15. #include <ext/pb_ds/assoc_container.hpp>
  16. #include <ext/pb_ds/tree_policy.hpp>
  17. using namespace __gnu_pbds;
  18. template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  19. //ostream& endl(ostream& os) {
  20. // return os << '\n';
  21. //}
  22. #define all(xxx) xxx.begin(), xxx.end()
  23. #define watch(xxx) cout << "value of " << #xxx << " is " << xxx << endl;
  24. template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
  25. template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
  26. template <typename T, typename U>
  27. ostream& operator<<(ostream& os, const pair<T, U>& A) {
  28. os << A.fi << " " << A.se;
  29. return os;
  30. }
  31. template <typename T>
  32. ostream& operator<<(ostream& os, const vector<T>& A) {
  33. for (size_t i = 0; i < A.size(); i++) {
  34. if (i) os << " ";
  35. os << A[i];
  36. }
  37. return os;
  38. }
  39. void scan(ll &a) { cin >> a; }
  40. void scan(char &a) { cin >> a; }
  41. void scan(double &a) { cin >> a; }
  42. void scan(long double &a) { cin >> a; }
  43. void scan(string &a) { cin >> a; }
  44. template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
  45. template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}
  46. template <class T> void scan(T &a) { cin >> a; }
  47. void IN() {}
  48. template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
  49. scan(head);
  50. IN(tail...);
  51. }
  52. void print() {
  53. cout << "\n";
  54. }
  55. template <class Head, class... Tail>
  56. void print(Head&& head, Tail&&... tail) {
  57. cout << head;
  58. if (sizeof...(Tail)) cout << " ";
  59. print(forward<Tail>(tail)...);
  60. }
  61. #ifdef LOCAL
  62. #include <algo/debug.h>
  63. #else
  64. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math,trapv")
  65. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
  66. #endif
  67. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  68. uniform_int_distribution<ll> distrib(0ll, 10ll);
  69. //constexpr ll MOD = 1e9+7;
  70. constexpr ll MOD = 1e9+7;
  71. void in(vector<ll> & a) {
  72. for (auto & zero_leaf : a) cin >> zero_leaf;
  73. }
  74. void in(vector<ll> & a, ll l, ll r) {
  75. for (ll i=l; i < r; i+=1) {
  76. cin >> a[i];
  77. }
  78. }
  79. void inn(vector<ll> & a, ll l, ll rr) {
  80. for (ll i=l; i <= rr; i+=1) {
  81. cin >> a[i];
  82. }
  83. }
  84. ll powm(ll a, ll b) {
  85. assert(b >= 0);
  86. ll d = 1;
  87. while (b) {
  88. if (b&1) d = (d*a) % MOD;
  89. b >>= 1;
  90. a = (a*a) % MOD;
  91. }
  92. return d;
  93. }
  94. ll powm(ll a, ll b, ll MODD) {
  95. assert(b >= 0);
  96. ll d = 1;
  97. while (b) {
  98. if (b&1) d = (d*a) % MODD;
  99. b >>= 1;
  100. a = (a*a) % MODD;
  101. }
  102. return d;
  103. }
  104. ll poww(ll a, ll b) {
  105. assert(b >= 0);
  106. ll d = 1;
  107. while (b) {
  108. if (b&1) d = (d*a);
  109. b >>= 1;
  110. a = (a*a);
  111. }
  112. return d;
  113. }
  114. ld poww(ld a, ll b) {
  115. assert(b >= 0);
  116. ld d = 1;
  117. while (b) {
  118. if (b&1) d = (d*a);
  119. b >>= 1;
  120. a = (a*a);
  121. }
  122. return d;
  123. }
  124. ll mul(ll a, ll b) {
  125. return (a*b)%MOD;
  126. }
  127. ll mul(ll a, ll b, ll MODD) {
  128. return (a*b)%MODD;
  129. }
  130. ll sum(ll a, ll b) {
  131. return (a+b)%MOD;
  132. }
  133. ll sum(ll a, ll b, ll MODD) {
  134. return (a+b)%MODD;
  135. }
  136. ll sub(ll a, ll b) {
  137. return (a-(b%MOD)+MOD)%MOD;
  138. }
  139. ll sub(ll a, ll b, ll MODD) {
  140. return (a-(b%MODD)+MODD)%MODD;
  141. }
  142. /*
  143. void copy_this () {
  144. ll n; cin >> n;
  145. ll n, k; cin >> n >> k;
  146. ll n, q; cin >> n >> q;
  147. ll a[n]; for (ll i=0; i < n; i+=1) cin >> a[i];
  148. vector<ll> a(n); for (ll i=0; i < n; i+=1) cin >> a[i];
  149. }
  150. */
  151.  
  152. void solve() {
  153. ll n; cin >> n;
  154. vector<pair<ld, ld>> a(n);
  155. for (ll i = 0; i < n; i += 1) {
  156. ll x, y;
  157. cin >> x >> y;
  158. a[i].first = x;
  159. a[i].second = y;
  160. }
  161. ll m; cin >> m;
  162. vector<pair<ld, ld>> b(m);
  163. for (ll i = 0; i < m; i += 1) {
  164. ll x, y;
  165. cin >> x >> y;
  166. b[i].first = x;
  167. b[i].second = y;
  168. }
  169. auto f = [&] (ld dx, ld dy) -> ld {
  170. ld maxi = 0;
  171. for (ll i = 0; i < n; i += 1) {
  172. for (ll j = 0; j < m; j += 1) {
  173. ld res = (a[i].first-b[j].first+dx)*(a[i].first-b[j].first+dx)+
  174. (a[i].second-b[j].second+dy)*(a[i].second-b[j].second+dy);
  175. maxi = max(maxi, res);
  176. }
  177. }
  178. return maxi;
  179. };
  180. ld YYY = -666;
  181. ld RES = -666;
  182. ld EPS = 1e-13;
  183. auto shit = [&] (ld x) {
  184. ld ly = -10, ry = 10;
  185. for (ll j = 0; j < 9000; j += 1) {
  186. ld midy = (ly+ry)/ld(2);
  187. if (f(x, midy) > f(x, midy+EPS)) {
  188. ly = midy;
  189. } else {
  190. ry = midy;
  191. }
  192. }
  193. YYY = ly;
  194. RES = f(x, ly);
  195. return RES;
  196. };
  197. ld lx = -10, rx = 10;
  198. for (ll i = 0; i < 2000; i += 1) {
  199. // cout << lx << " " << rx << endl;
  200. ld midx = (lx+rx)/ld(2);
  201. if (shit(midx) > shit(midx+EPS)) {
  202. lx = midx;
  203. } else {
  204. rx = midx;
  205. }
  206.  
  207. }
  208. cout << sqrtl(RES) << " " << lx << " " << YYY << endl;
  209. }
  210.  
  211. int32_t main(int32_t argc, char* argv[]) {
  212. // ifstream cin("distance.in");
  213. // ofstream cout("distance.out");
  214. cout << fixed << setprecision(17);
  215. bool use_fast_io = true;
  216. for (int32_t i = 1; i < argc; ++i) {
  217. if (string(argv[i]) == "-local-no-fast-io") {
  218. use_fast_io = false;
  219. // cout << "No fastIO" << endl;
  220. break;
  221. }
  222. }
  223. if (use_fast_io) {
  224. ios::sync_with_stdio(false);
  225. cin.tie(nullptr);
  226. cout.tie(nullptr);
  227. cerr.tie(nullptr);
  228. clog.tie(nullptr);
  229. }
  230. ll tt = 1;
  231. // cin >> tt;
  232.  
  233. while (tt--) {
  234. solve();
  235. }
  236. return 0;
  237. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement