1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. #define endl "\n"
  6. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  7. #define ALL(x) x.begin(),x.end()
  8. #define SORT(x) sort(ALL(x))
  9. #define FOR(a,b,c) for(int (a)= (b);(a)<(c);++(a))
  10. #define REP(a,b) FOR(a,0,b)
  11. #define mp make_pair
  12. #define pb push_back
  13. #define pll pair<ll,ll>
  14. #define pii pair<int,int>
  15. #define vl vector<ll>
  16. #define vi vector<int>
  17. #define f first
  18. #define s second
  19. ll ttt = 1, case_ = 0;
  20. ll n, m, x, y, c;
  23. template <class myType>
  24. void print_arr(myType &arr, ll L, string sep){ REP(i,L) {
  25. cout << arr[i]; if (i < L-1) cout << sep;
  26. } cout << endl; return; }
  28. /*
  29. Try every triangle.
  30. If every triangle fails, we try quadrilaterals as follows:
  31. -find all pairs of points such that the blue star lies on the line connecting them
  32. -if we can find two such pairs of points, all distinct, not all collinear, then that's an answer
  33. */
  34. int sign_(ll a) {
  35. if (a > 0) return 1;
  36. if (a < 0) return -1;
  37. return 0;
  38. }
  40. bool pt_inside(pll S, pll A, pll B, pll C)
  41. {
  42. ll as_x = S.f-A.f;
  43. ll as_y = S.s-A.s;
  44. bool s_ab = (B.f-A.f)*as_y-(B.s-A.s)*as_x > 0;
  45. if((C.f-A.f)*as_y-(C.s-A.s)*as_x > 0 == s_ab) return 0;
  46. if((C.f-B.f)*(S.s-B.s)-(C.s-B.s)*(S.f-B.f) > 0 != s_ab) return 0;
  47. vector<pll> PTS = {A, B, C};
  48. for (int i = 0; i < 3; i++) {
  49. for(int j = i+1; j < 3; j++) {
  50. pll g1, g2;
  51. g1 = mp(PTS[i].f - S.f, PTS[i].s - S.s);
  52. g2 = mp(PTS[j].f - S.f, PTS[j].s - S.s);
  53. if (g1.f < 0) {
  54. g1.f *= -1;
  55. g1.s *= -1;
  56. }
  57. if (g2.f < 0) {
  58. g2.f *= -1;
  59. g2.s *= -1;
  60. }
  61. if (g1.f == 0) g1.s = abs(g1.s);
  62. if (g2.f == 0) g2.s = abs(g2.s);
  63. ll G1 = __gcd(g1.f, g1.s), G2 = __gcd(g2.f, g2.s);
  64. g1.f /= G1;
  65. g1.s /= G1;
  66. g2.f /= G2;
  67. g2.s /= G2;
  68. if (g1 == g2) return 0;
  69. }
  70. }
  71. return 1;
  72. }
  74. ld dist(pll a, pll b) {
  75. ld xx, yy;
  76. xx = (ld) a.f - (ld) b.f;
  77. yy = (ld) a.s - (ld) b.s;
  78. return (ld) sqrtl( xx*xx + yy*yy );
  79. }
  82. void solve() {
  83. case_++;
  84. cout << "Case #" << case_ << ": ";
  85. cin >> n;
  86. vector<pll> pts(n);
  87. REP(i,n) {
  88. cin >> pts[i].f >> pts[i].s;
  89. }
  90. pll S;
  91. cin >> S.f >> S.s;
  92. ld const BIG = (ld) 1e18;
  93. ld ans = BIG;
  94. ld eps = 0.01;
  95. for(int i = 0; i < n; i++) {
  96. for(int j = i+1; j < n; j++) {
  97. for(int k = j+1; k < n; k++) {
  98. if (pt_inside(S, pts[i], pts[j], pts[k])) {
  99. ans = min(ans, dist(pts[i], pts[j]) + dist(pts[j], pts[k]) + dist(pts[k], pts[i]));
  100. //cout << pts[i].f << " " << pts[i].s << " " << pts[j].f << " " << pts[j].s << " " << pts[k].f << " " << pts[k].s << ans << endl;
  101. }
  102. }
  103. }
  104. }
  105. // calculate the gradient of the line connecting the blue star with the white star
  106. // store points by gradient
  107. // for each gradient, if > 1 point and there are points either side of the blue star, then we have a candidate pair
  108. map<pll, vector<pll>> grads;
  109. for(int i = 0; i < n; i++) {
  110. ll dx, dy;
  111. dx = S.f - pts[i].f;
  112. dy = S.s - pts[i].s;
  113. if (dx < 0) {
  114. dy = -dy;
  115. dx = -dx;
  116. }
  117. ll G = __gcd(abs(dx), abs(dy));
  118. dx /= G;
  119. dy /= G;
  120. if (dx == 0) dy = abs(dy);
  121. grads[mp(dx, dy)].pb(pts[i]);
  122. }
  123. map<pll,vector<pll>>::iterator it = grads.begin();
  124. // dx is always >= 0
  125. vector<pair<pll, pll>> cands;
  126. while (it != grads.end()){
  127. SORT(it->s);
  128. vector<pll> p = it->s;
  129. //cout << it->f.f << " " << it->f.s << endl;
  130. for(int i = 0; i < p.size() - 1; i++) {
  131. //cout << p[i].f << " " << p[i].s << " " << p[i+1].f << " " << p[i+1].s << endl;
  132. if (sign_(p[i].f - S.f) == sign_(S.f - p[i+1].f) && sign_(p[i].s - S.s) == sign_(S.s - p[i+1].s)) {
  133. cands.pb(mp(p[i], p[i+1]));
  134. break;
  135. }
  136. }
  137. it++;
  138. }
  139. for(int i = 0; i < cands.size(); i++) {
  140. //cout << cands[i].f.f << " " << cands[i].f.s << " " << cands[i].s.f << " " << cands[i].s.s << endl;
  141. for(int j = i+1; j < cands.size(); j++) {
  142. ans = min(ans, dist(cands[i].f, cands[j].f) + dist(cands[i].f, cands[j].s) + dist(cands[i].s, cands[j].f) + dist(cands[i].s, cands[j].s));
  143. }
  144. }
  145. if (abs(ans - (ld) 1e18) < eps) {
  146. cout << "IMPOSSIBLE" << endl;
  147. return;
  148. }
  149. cout << setprecision(20) << ans << endl;
  150. return;
  151. }
  153. int main(){
  154. quick;
  155. cin >> ttt;
  156. while (ttt--) solve();
  157. return 0;
  158. }