fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ld long double
  5. #define all(x) x.begin(), x.end()
  6. const int N = 1e6 + 5;
  7.  
  8. using P = array<int, 2>;
  9. void solve(int tc) {
  10.     int n, k;
  11.     cin >> n >> k;
  12.     vector<P> points(n);
  13.     for (auto &[x, y] : points) {
  14.         cin >> x >> y;
  15.     }
  16.     auto quad = [](P p) {
  17.         if (p[0] >= 0 && p[1] >= 0) return 1;
  18.         if (p[0] < 0 && p[1] >= 0) return 2;
  19.         if (p[0] < 0 && p[1] < 0) return 3;
  20.         return 4;
  21.     };
  22.     auto cross = [](P a, P b) { return a[0] * b[1] - a[1] * b[0]; };
  23.     auto dist2 = [](P a) { return a[0] * a[0] + a[1] * a[1]; };
  24.     auto xangle = [](P a) -> long double {
  25.         long double res = atan2l(a[1], a[0]);
  26.         // cout<<res<<endl;
  27.         if (res < 0) {
  28.             res += (2 * acos(-1));
  29.         }
  30.         return res;
  31.     };
  32.     auto angle = [&](P a, P b) {
  33.         long double aA = xangle(a);
  34.         long double aB = xangle(b);
  35.         if (aB < aA) {
  36.             aB += (2 * acos(-1));
  37.         }
  38.         return aB - aA;
  39.     };
  40.     sort(all(points), [&](P a, P b) {
  41.         if (quad(a) != quad(b)) {
  42.             return quad(a) < quad(b);
  43.         }
  44.         if (cross(a, b) != 0) {
  45.             return cross(a, b) > 0;
  46.         }
  47.         return dist2(a) < dist2(b);
  48.     });
  49.     // for(auto [x,y]:points){
  50.     //     cout<<x<<" "<<y<<endl;
  51.     // }
  52.     auto reduce = [](P &a) -> P {
  53.         P F = a;
  54.         // return {1LL,1LL};
  55.         // cout << a[0] << " " << a[1] << endl;
  56.         // return {1LL, 1LL};
  57.  
  58.         int g = __gcd(a[0], a[1]);
  59.         // cout << g << " ";0
  60.         // return {1, 1};
  61.         F[0] /= g;
  62.         F[1] /= g;
  63.         int s1 = F[0] >= 0;
  64.         int s2 = F[1] >= 0;
  65.         F[0] = abs(F[0]);
  66.         F[1] = abs(F[1]);
  67.  
  68.         if (F[1] == 0) {
  69.             return {s1, 0};
  70.         } else if (F[0] == 0) {
  71.             return {0, 0};
  72.         } else {
  73.             return {s1 * F[0], F[1]};
  74.         }
  75.     };
  76.     // return;
  77.     long double ans = 0;
  78.     map<array<int,3>, int> mp;
  79.     for(int i = 0; i<n;i++){
  80.  
  81.     }
  82.     for (int i = 0; i < n; i++) {
  83.         auto r = reduce(points[i]);
  84.         int K = k - mp[{r[0],r[1],quad(points[i])}];
  85.         int next = (i + K) % n;
  86.         ans = max(ans, angle(points[i], points[next]));
  87.         mp[{r[0],r[1],quad(points[i])}]++;
  88.     }
  89.     const double eps = 1e-8;
  90.     if (ans < eps) ans = 2 * acos(-1);
  91.     cout << fixed << setprecision(10) << ans << "\n";
  92. }
  93.  
  94. signed main() {
  95.     ios::sync_with_stdio(false);
  96.     cin.tie(NULL);
  97.     int t = 1;
  98.     cin >> t;
  99.     for (int i = 1; i <= t; i++) {
  100.         // cout << "Case " << i << ":\n";
  101.         solve(i);
  102.     }
  103.     return 0;
  104. }
Success #stdin #stdout 0.01s 5352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6.2831853072
https://ideone.com/na9L4M
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!