fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef long double ld;
  8. const ld PI = acosl(-1.0L);
  9. const ld EPS = 1e-12L;
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.  
  15.     int T;
  16.     cin >> T;
  17.  
  18.     while (T--) {
  19.         int n, m;
  20.         ld z;
  21.         cin >> n >> m >> z;
  22.  
  23.         vector<ld> px(n), py(n);
  24.         for (int i = 0; i < n; i++) {
  25.             cin >> px[i] >> py[i];
  26.         }
  27.  
  28.         ld half_z = z / 2.0L;
  29.  
  30.         vector<pair<ld, int>> events;
  31.  
  32.         for (int i = 0; i < n; i++) {
  33.             ld x = px[i];
  34.             ld y = py[i];
  35.             ld r = sqrtl(x*x + y*y);
  36.             ld alpha = atan2l(y, x);
  37.             if (alpha < 0) alpha += 2*PI;
  38.  
  39.             ld ratio = half_z / r;
  40.  
  41.             ld lo, hi;
  42.             if (ratio >= 1.0L) {
  43.                 lo = alpha - PI/2;
  44.                 hi = alpha + PI/2;
  45.             } else {
  46.                 ld delta = asinl(ratio);
  47.                 lo = alpha - delta;
  48.                 hi = alpha + delta;
  49.             }
  50.  
  51.             // Normalize lo to [0, 2*PI)
  52.             while (lo < 0) lo += 2*PI;
  53.             while (lo >= 2*PI) lo -= 2*PI;
  54.             // Normalize hi to [0, 2*PI)
  55.             while (hi < 0) hi += 2*PI;
  56.             while (hi >= 2*PI) hi -= 2*PI;
  57.  
  58.             if (lo <= hi) {
  59.                 events.push_back({lo, 1});
  60.                 events.push_back({hi, -1});
  61.             } else {
  62.                 // Interval wraps around 0
  63.                 events.push_back({0.0L, 1});
  64.                 events.push_back({hi, -1});
  65.                 events.push_back({lo, 1});
  66.                 events.push_back({2*PI, -1});
  67.             }
  68.         }
  69.  
  70.         sort(events.begin(), events.end(), [](const pair<ld,int>& a, const pair<ld,int>& b) {
  71.             if (fabsl(a.first - b.first) < EPS) return a.second > b.second;
  72.             return a.first < b.first;
  73.         });
  74.  
  75.         int max_count = 0, count = 0;
  76.         for (const auto& ev : events) {
  77.             count += ev.second;
  78.             max_count = max(max_count, count);
  79.         }
  80.  
  81.         cout << (max_count >= m ? "Yes" : "No") << "\n";
  82.     }
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uVBKni
language:
C++14 (clang 8.0)
created:
13 hours 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!