fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7.  
  8. int const NMAX = 1e5;
  9. int n, k;
  10. pair<int, int> p[1 + NMAX];
  11.  
  12. long long dist(int i, int j) {
  13.     return 1LL * (p[i].x - p[j].x) * (p[i].x - p[j].x) + 1LL * (p[i].y - p[j].y) * (p[i].y - p[j].y);
  14. }
  15.  
  16. long long binarysearch(long long from, long long to, double val) {
  17.     if (from < to) {
  18.         long long guess = (from + to)/2;
  19.         if (1.0 * guess * guess < val) {
  20.         	return binarysearch(guess+1, to, val);
  21.         } else {
  22.         	return binarysearch(from, guess, val);
  23.         }
  24.     }
  25.     return from;
  26. }
  27.  
  28. int main() {
  29.     cin >> n >> k;
  30.     for (int i = 1; i <= n; i++) {
  31.         cin >> p[i].x >> p[i].y;
  32.     }
  33.     int l = 1, r = 1;
  34.     long long max_dist = 0;
  35.     int counter = 0;
  36.     while (l <= n) {
  37.         if ((r == n && dist(l, 1) > dist(l, r)) || (r != n && dist(l, r+1) > dist(l, r))) {
  38.             r++;
  39.             if (r > n) {
  40.                 r = 1;
  41.             }
  42.         } else {
  43.             long long new_dist = dist(l, r);
  44.             if (new_dist == max_dist) {
  45.                 counter++;
  46.             } else if (new_dist > max_dist) {
  47.                 counter = 1;
  48.                 max_dist = new_dist;
  49.             }
  50.             l++;
  51.         }
  52.     }
  53.     counter /= 2;
  54.     long long sqr = binarysearch(1, max_dist, max_dist);
  55.     if (sqr * sqr == max_dist) {
  56.         long long ans = k / (2 * sqr);
  57.         if (2 * ans * sqr == k && ans > counter || 2 * ans * sqr != k) {
  58.             ans++;
  59.         }
  60.         cout << ans << "\n";
  61.     } else {
  62.         long long ans = binarysearch(1, 1e18, (1.0 * k * k) / (4.0 * max_dist));
  63.         cout << ans << "\n";
  64.     }
  65.     //cout << k << " " << sqr << "\n";
  66. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
16 80
4 0
3 1
2 2
1 3
0 4
-1 3
-2 2
-3 1
-4 0
-3 -1
-2 -2
-1 -3
0 -4
1 -3
2 -2
3 -1
stdout
copy 
6
https://ideone.com/4ZGe5o
language:
C++14 (gcc 8.3)
created:
4 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!