Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <string.h>
  6. #include <memory.h>
  7. #include <utility>
  8. #include <queue>
  9. #include <algorithm>
  10. #include <cmath>
  11. #include <map>
  12. #include <set>
  13. using namespace std;
  14.  
  15. #define mp make_pair
  16. #define pb push_back
  17. #define sz(a) int((a).size())
  18. #define forn(i, n) for (int i=0; i<(n); ++i)
  19.  
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair<int,int> pii;
  23.  
  24. const int maxn = 5120;
  25. const ld eps = 1e-8;
  26. const ld pi = acos(-1.0);
  27.  
  28. struct point
  29. {
  30.   int x, y;
  31.   ld ang;
  32. };
  33.  
  34.  
  35. bool operator<(const point& a, const point& b)
  36. {
  37.   if (fabs(a.ang-b.ang) > eps) return a.ang < b.ang;
  38.   if (a.x != b.x) return a.x < b.x;
  39.   return a.y < b.y;
  40. }
  41.  
  42. point a[maxn];
  43. point b[maxn];
  44. int n, k, m;
  45.  
  46. int main()
  47. {
  48.   freopen("a.in", "r", stdin);
  49.  
  50.   int tc; scanf("%d", &tc);
  51.   while (tc--)
  52.   {
  53.     scanf("%d", &k);
  54.     n = 4*k+5;
  55.     forn (i, n)
  56.     {
  57.       int x, y;
  58.       scanf("%d %d", &x, &y);
  59.       a[i].x = x, a[i].y = y;
  60.     }
  61.  
  62.     ld res = 1e30;
  63.  
  64.     forn (i, n)
  65.     {
  66.       m = 0;
  67.       forn (j, n) if (i!=j)
  68.       {
  69.         b[m] = a[j];
  70.         b[m].x -= a[i].x, b[m].y -= a[i].y;
  71.         b[m].ang = atan2(1.0*b[m].y, 1.0*b[m].x);
  72.         ++m;
  73.       }
  74.       sort(b, b+m);
  75.       forn (j, m)
  76.       {
  77.         ld cur = 0;
  78.         ld lst = b[j].ang;
  79.         for (int q=1; q<=4; ++q)
  80.         {
  81.           ld ang = b[(j+q*k+q)%m].ang;
  82.           ld dx = ang - lst;
  83.           lst = ang;
  84.           while (dx < -eps) dx += 2*pi;          
  85.           if (dx > pi - eps) cur = 1e30;
  86.           else
  87.           {
  88.             cur += fabs(cos(dx) / sin(dx));
  89.           }          
  90.         }
  91. //        puts("----");
  92. //        printf("%.6f\n", double(cur));
  93.         res = min(res, cur);
  94.       }
  95.     }
  96.  
  97.     if (res > 1e29) puts("Impossible");
  98.     else printf("%.10f\n", double(res));
  99.  
  100.   }
  101.  
  102.  
  103.  
  104.   return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement