Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- #include <string>
- #include <string.h>
- #include <memory.h>
- #include <utility>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <map>
- #include <set>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define sz(a) int((a).size())
- #define forn(i, n) for (int i=0; i<(n); ++i)
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- const int maxn = 5120;
- const ld eps = 1e-8;
- const ld pi = acos(-1.0);
- struct point
- {
- int x, y;
- ld ang;
- };
- bool operator<(const point& a, const point& b)
- {
- if (fabs(a.ang-b.ang) > eps) return a.ang < b.ang;
- if (a.x != b.x) return a.x < b.x;
- return a.y < b.y;
- }
- point a[maxn];
- point b[maxn];
- int n, k, m;
- int main()
- {
- freopen("a.in", "r", stdin);
- int tc; scanf("%d", &tc);
- while (tc--)
- {
- scanf("%d", &k);
- n = 4*k+5;
- forn (i, n)
- {
- int x, y;
- scanf("%d %d", &x, &y);
- a[i].x = x, a[i].y = y;
- }
- ld res = 1e30;
- forn (i, n)
- {
- m = 0;
- forn (j, n) if (i!=j)
- {
- b[m] = a[j];
- b[m].x -= a[i].x, b[m].y -= a[i].y;
- b[m].ang = atan2(1.0*b[m].y, 1.0*b[m].x);
- ++m;
- }
- sort(b, b+m);
- forn (j, m)
- {
- ld cur = 0;
- ld lst = b[j].ang;
- for (int q=1; q<=4; ++q)
- {
- ld ang = b[(j+q*k+q)%m].ang;
- ld dx = ang - lst;
- lst = ang;
- while (dx < -eps) dx += 2*pi;
- if (dx > pi - eps) cur = 1e30;
- else
- {
- cur += fabs(cos(dx) / sin(dx));
- }
- }
- // puts("----");
- // printf("%.6f\n", double(cur));
- res = min(res, cur);
- }
- }
- if (res > 1e29) puts("Impossible");
- else printf("%.10f\n", double(res));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement