提出 #35595508

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
vector<tuple<int,int,int> > abc;
const double PI=acos(-1);

double xy2theta(double x,double y){ // (x,y) -> theta
  if(x>=0 && y>=0) return atan(y/x);
  if(x<0 && y>=0) return PI/2+atan(-x/y);
  if(x<0 && y<0) return PI+atan(y/x);
  return 3*PI/2+atan(-x/y);
}

pair<double,double> solve(double A,double B,double C){ // Ax^2+Bx+C=0
  return {(-B+sqrt(abs(B*B-4*A*C)))/(2*A),(-B-sqrt(abs(B*B-4*A*C)))/(2*A)};
}

ll cross(const vector<pair<int,int>>&ij){ // 线段相交数
  vector<int>fen(ij.size()*2);//fenwick
  auto query=[&](int x){
    int r=0;
    for(int i=x+1;i;i-=(i&-i)) r+=fen[i-1];
    return r;
  };
  auto add=[&](int x){
    for(int i=x+1;i<=(int)fen.size();i+=(i&-i)) fen[i-1]++;
  };

  ll r=0;
  for(auto [i,j]:ij){
    r+=query(j-1)-query(i); // pi < i < pj < j, 查询 [i+1,j-1]
    add(j);
  }
  return r;
}

int f(double radius){
  vector<pair<double,double>> lr;
  for(auto [a,b,c]:abc)if(abs(c)/sqrt(a*a+b*b) < radius){
    double x0,y0,x1,y1;
    if(a != 0){
      tie(y0,y1) = solve(a*a+b*b,2*b*c,c*c-a*a*radius*radius);
      x0 = -(b*y0+c)/a;
      x1 = -(b*y1+c)/a;
    }else{
      tie(x0,x1) = solve(a*a+b*b,2*a*c,c*c-b*b*radius*radius);
      y0 = -(a*x0+c)/b;
      y1 = -(a*x1+c)/b;
    }
    auto l = xy2theta(x0,y0);
    auto r = xy2theta(x1,y1);
    if(l>r)swap(l,r);
    lr.push_back({l,r});
  }
  vector<double> p;
  for(auto[l,r]:lr){
    p.push_back(l);
    p.push_back(r);
  }
  sort(begin(p),end(p));
  vector<pair<int,int> >ij;
  for(auto [l,r]:lr)ij.push_back({
      lower_bound(begin(p),end(p),l)-begin(p),
      lower_bound(begin(p),end(p),r)-begin(p)
  });
  sort(begin(ij),end(ij));
  return cross(ij);
}

int main(){
  int n = read();
  int k = read();
  rep(i,0,n)abc.push_back({read(),read(),read()});

  double l = 0;
  double r = 4e6;
  while(r-l>1e-6){
    double mid=(l+r)/2;
    (f(mid)<k?l:r)=mid;
  }
  printf("%.15lf\n",l);
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘ll read()’:
./Main.cpp:5:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果