Guest User

code

a guest
Mar 10th, 2021
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //credits: Benq
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using db = long double; // or double, if TL is tight
  7. using str = string; // yay python!
  8.  
  9. using pi = pair<int, int>;
  10. using pl = pair<ll, ll>;
  11. using pd = pair<db, db>;
  12.  
  13. using vi = vector<int>;
  14. using vb = vector<bool>;
  15. using vl = vector<ll>;
  16. using vd = vector<db>;
  17. using vs = vector<str>;
  18. using vpi = vector<pi>;
  19. using vpl = vector<pl>;
  20. using vpd = vector<pd>;
  21.  
  22. #define tcT template<class T
  23. #define tcTU tcT, class U
  24. // ^ lol this makes everything look weird but I'll try it
  25. tcT> using V = vector<T>;
  26. tcT, size_t SZ > using AR = array<T, SZ>;
  27. tcT > using PR = pair<T, T>;
  28.  
  29. // pairs
  30. #define mp make_pair
  31. #define f first
  32. #define s second
  33.  
  34. // vectors
  35. // oops size(x), rbegin(x), rend(x) need C++17
  36. #define sz(x) int((x).size())
  37. #define bg(x) begin(x)
  38. #define all(x) bg(x), end(x)
  39. #define rall(x) x.rbegin(), x.rend()
  40. #define sor(x) sort(all(x))
  41. #define rsz resize
  42. #define ins insert
  43. #define ft front()
  44. #define bk back()
  45. #define pb push_back
  46. #define eb emplace_back
  47. #define pf push_front
  48. #define rtn return
  49.  
  50. #define lb lower_bound
  51. #define ub upper_bound
  52. tcT > int lwb(V<T>& a, const T& b) { return int(lb(all(a), b) - bg(a)); }
  53.  
  54. // loops
  55. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  56. #define F0R(i,a) FOR(i,0,a)
  57. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  58. #define R0F(i,a) ROF(i,0,a)
  59. #define rep(a) F0R(_,a)
  60. #define each(a,x) for (auto& a: x)
  61.  
  62. //optimization & debug
  63. #define francesco_bernoulli ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  64. #define DBG(x) cerr << #x << " = " << x << endl;
  65.  
  66. const int MOD = 1e9 + 7; // 998244353;
  67. const int MX = 2e5 + 5;
  68. const ll INF = 1e18; // not too close to LLONG_MAX
  69. const db PI = acos((db)-1);
  70. const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
  71. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  72. template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
  73.  
  74. // bitwise ops
  75. // also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
  76. constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
  77. constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
  78. return x == 0 ? 0 : 31 - __builtin_clz(x);
  79. } // floor(log2(x))
  80. constexpr int p2(int x) { return 1 << x; }
  81. constexpr int msk2(int x) { return p2(x) - 1; }
  82.  
  83. ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
  84. ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down
  85.  
  86. tcT > bool ckmin(T& a, const T& b) {
  87. return b < a ? a = b, 1 : 0;
  88. } // set a = min(a,b)
  89. tcT > bool ckmax(T& a, const T& b) {
  90. return a < b ? a = b, 1 : 0;
  91. }
  92.  
  93. tcT > void remDup(vector<T>& v) { // sort and remove duplicates
  94. sort(all(v)); v.erase(unique(all(v)), end(v));
  95. }
  96.  
  97. long double distance(long double a, long double b, long double c, long double d) {
  98. long double x = a - c;
  99. long double y = b - d;
  100. return sqrt((y * y) + (x * x));
  101. }
  102.  
  103. void solve() {
  104.  
  105. int n;
  106.  
  107. cin >> n;
  108.  
  109. //x = 0 so miner
  110. //y = 0 so diamond
  111.  
  112. vector<pair<long double, long double>> miners;
  113. vector<pair<long double, long double>> diamonds;
  114. int x, y;
  115. F0R(i, 2 * n) {
  116.  
  117. cin >> x >> y;
  118.  
  119. if (!x) {
  120. y = abs(y);
  121. long double x1 = static_cast<long double>(x), y1 = static_cast<long double>(y);
  122. miners.push_back({ x1, y1 });
  123. }
  124. else {
  125. x = abs(x);
  126. long double x1 = static_cast<long double>(x), y1 = static_cast<long double>(y);
  127. diamonds.push_back({ y1, x1 });
  128. }
  129. }
  130.  
  131. sort(rall(miners));
  132. sort(rall(diamonds));
  133.  
  134. long double ans = 1000000000.0, mini = 0;
  135.  
  136. F0R(i, n) {
  137. // cout << i+1 << ". \n";
  138. cout << miners[i].first << " " << diamonds[i].second << "\n";
  139. cout << miners[i].second << " " << diamonds[i].first << "\n";
  140. // cout << "\n";
  141. mini += distance(miners[i].first, diamonds[i].second, miners[i].second, diamonds[i].first);
  142. }
  143.  
  144. ans = min(ans, mini);
  145.  
  146. sort(all(miners));
  147. sort(rall(diamonds));
  148.  
  149. mini = 0;
  150.  
  151. F0R(i, n) {
  152. // cout << i+1 << ". \n";
  153. // cout << miners[i].first << " " << diamonds[i].second << "\n";
  154. // cout << miners[i].second << " " << diamonds[i].first << "\n";
  155. // cout << "\n";
  156. mini += distance(miners[i].first, diamonds[i].second, miners[i].second, diamonds[i].first);
  157. }
  158.  
  159. ans = min(ans, mini);
  160.  
  161. cout.precision(15);
  162. cout << fixed << ans << "\n";
  163.  
  164.  
  165. }
  166.  
  167. int main() {
  168.  
  169. francesco_bernoulli;
  170.  
  171. int t = 1;
  172.  
  173. cin >> t;
  174.  
  175. while (t--)
  176. solve();
  177.  
  178. return 0;
  179. }
  180.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×