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