Submission #1630637

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<double, ll> pdl;

struct point { double x, y; };
struct line { point p, q; };

ll N, K;

double distance(line l, point p) {
  double ux = l.q.x - l.p.x;
  double uy = l.q.y - l.p.y;
  double vx = p.x - l.p.x;
  double vy = p.y - l.p.y;
  double cross = abs(ux * vy - uy * vx);
  double ul = sqrt(ux * ux + uy * uy);
  return cross / ul;
}

int main(void) {
  cin >> N >> K;

  vector<pdl> triangles;
  for(ll i = 1; i * 3 <= N; i++) {
    for(ll j = i * 2; j <= (i + N) / 2; j++) {
      double theta = 2 * M_PI / N;
      point p1 = (point) { 1, 0 };
      point p2 = (point) { cos(theta * i), sin(theta * i) };
      point p3 = (point) { cos(theta * j), sin(theta * j) };
      double a = sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
      double h = distance((line) { p1, p2 }, p3);
      double s = a * h / 2;
      ll cnt, e1 = i, e2 = j - i, e3 = N - j;
      if(e1 == e2 && e2 == e3) cnt = i;
      else if(e1 == e2 || e2 == e3 || e3 == e1) cnt = N;
      else cnt = N * 2;
      triangles.push_back(pdl(s, cnt));
    }
  }

  sort(triangles.begin(), triangles.end());

  ll sum = 0;
  REP(i, 0, triangles.size()) {
    sum += triangles[i].second;
    if(sum >= K) {
      printf("%.15lf\n", triangles[i].first);
      return 0;
    }
  }
}

Submission Info

Judge Result