Submission #10460002


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

using D = long double;
const D PI = acos(-1.0);
const D EPS = 1e-10;
struct P {
  D x, y;
  P(D x=0, D y=0) : x(x), y(y) {}

  P& operator+=(const P& o) { x += o.x; y += o.y; return *this; }
  P& operator-=(const P& o) { x -= o.x; y -= o.y; return *this; }
  P& operator*=(const P& o) { return *this = {x*o.x - y*o.y, x*o.y + y*o.x}; }
  P& operator*=(const D& r) { x *= r; y *= r; return *this; }
  P& operator/=(const D& r) { x /= r; y /= r; return *this; }
  P operator-() const { return {-x, -y}; }

  D norm() const { return x*x + y*y; }
  D abs() const { return sqrt(norm()); }
  D arg() const { return atan2(y, x); }
  bool isZero() const { return std::abs(x) < EPS && std::abs(y) < EPS; }
  /** 象限 */
  int orth() const { return y >= 0 ? (x >= 0 ? 1 : 2) : (x < 0 ? 3 : 4); }
  static P polar(const D& rho, const D& theta = 0) { return {rho * cos(theta), rho * sin(theta)}; }
};
std::ostream &operator<<(std::ostream &os, P const &p) { return os << "(" << p.x << ", " << p.y << ")"; }
P operator+(const P& p, const P& q) { return P(p) += q; }
P operator-(const P& p, const P& q) { return P(p) -= q; }
P operator*(const P& p, const P& q) { return P(p) *= q; }
P operator*(const P& p, const D& r) { return P(p) *= r; }
P operator/(const P& p, const D& r) { return P(p) /= r; }
P operator*(const D& r, const P& p) { return P(p) *= r; }
P operator/(const D& r, const P& p) { return P(p) /= r; }

struct C : public P {
  D r;
  C() {}
  C(const P &p, D r):P(p),r(r){}
};

// 2円の交点
vector<P> intersectionCC(const C& c1, const C& c2) {
  vector<P> ret;
  D d = (c1 - c2).abs();
  P diff = (c2 - c1) / d;
  if( c1.r + c2.r < d - EPS ) {                        // 離れていて交点0

  } else if( d < EPS && abs(c1.r - c2.r) < EPS ) {     // 2円が重なる

  } else if( abs( c1.r + c2.r - d ) < EPS ) {          // 外側で1点で接する
    ret.push_back( c1 + diff * c1.r );
  } else if( abs( c1.r - c2.r ) > d + EPS ) {          // 内側に含む。交点0

  } else if( abs( abs( c1.r - c2.r ) - d ) < EPS) {    // 内側で1点で接する
    ret.push_back( c1 + diff * c1.r );
  } else {                                            // 2点で交わる
//     assert( d < c1.r + c2.r );
    D rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
    D rs = sqrt(c1.r*c1.r - rc*rc);

    ret.push_back( c1 + diff * P(rc, -rs) );
    ret.push_back( c1 + diff * P(rc, rs) );
  }
  return ret;
}

bool possible(int N, int K, const vector<C> cs) {
  vector<P> cand;
  REP(i, N) cand.push_back(cs[i]);
  REP(i, N) {
    REP(j, i) {
      auto v = intersectionCC(cs[i], cs[j]);
      for (P p : v)
        cand.push_back(p);
    }
  }
  for (P p : cand) {
    int in = 0;
    REP(i, N) {
      if ((cs[i] - p).abs() <= cs[i].r + EPS) in++;
    }
    if (in >= K) return true;
  }
  return false;
}

int main2() {
  int N = nextInt();
  int K = nextInt();

  vector<C> vs(N);
  vector<double> c(N);
  REP(i, N) {
    double x = nextInt();
    double y = nextInt();
    vs[i] = C(P(x, y), 0);
    c[i] = nextInt();
  }

  double hi = 1000000000;
  double lo = 0;
  REP(step, 200) {
    double ans = (hi + lo) / 2.0;
    REP(i, N) {
      vs[i].r = ans / c[i];
    }
    if (possible(N, K, vs)) {
      hi = ans;
    } else {
      lo = ans;
    }
  }
  printf("%.10f\n", hi);
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Submission Info

Submission Time
Task F - Yakiniku Optimization Problem
User hs484
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4013 Byte
Status AC
Exec Time 124 ms
Memory 432 KB

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:14:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int nextInt() { int x; scanf("%d", &x); return x;}
                                       ^
./Main.cpp: In function ‘ll nextLong()’:
./Main.cpp:15:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll nextLong() { ll x; scanf("%lld", &x); return x;}
                                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 67
Set Name Test Cases
Sample 00-sample-00, 00-sample-01
All 00-sample-00, 00-sample-01, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 02-random-00, 02-random-01, 02-random-02, 02-random-03, 02-random-04, 02-random-05, 02-random-06, 02-random-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 03-killer-00, 03-killer-01, 03-killer-02
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 2 ms 256 KB
01-handmade-00 AC 1 ms 256 KB
01-handmade-01 AC 1 ms 256 KB
01-handmade-02 AC 9 ms 384 KB
01-handmade-03 AC 52 ms 428 KB
01-handmade-04 AC 90 ms 428 KB
01-handmade-05 AC 99 ms 424 KB
01-handmade-06 AC 45 ms 428 KB
01-handmade-07 AC 58 ms 432 KB
01-handmade-08 AC 89 ms 408 KB
01-handmade-09 AC 88 ms 412 KB
01-handmade-10 AC 1 ms 256 KB
01-handmade-11 AC 2 ms 256 KB
02-random-00 AC 14 ms 384 KB
02-random-01 AC 79 ms 428 KB
02-random-02 AC 25 ms 384 KB
02-random-03 AC 112 ms 420 KB
02-random-04 AC 98 ms 432 KB
02-random-05 AC 15 ms 384 KB
02-random-06 AC 44 ms 416 KB
02-random-07 AC 37 ms 384 KB
02-random-08 AC 84 ms 416 KB
02-random-09 AC 34 ms 384 KB
02-random-10 AC 61 ms 416 KB
02-random-11 AC 45 ms 416 KB
02-random-12 AC 69 ms 424 KB
02-random-13 AC 39 ms 256 KB
02-random-14 AC 67 ms 416 KB
02-random-15 AC 39 ms 384 KB
02-random-16 AC 30 ms 384 KB
02-random-17 AC 12 ms 256 KB
02-random-18 AC 85 ms 412 KB
02-random-19 AC 85 ms 412 KB
02-random-20 AC 84 ms 412 KB
02-random-21 AC 37 ms 416 KB
02-random-22 AC 80 ms 416 KB
02-random-23 AC 118 ms 428 KB
02-random-24 AC 67 ms 420 KB
02-random-25 AC 24 ms 384 KB
02-random-26 AC 47 ms 384 KB
02-random-27 AC 22 ms 384 KB
02-random-28 AC 17 ms 384 KB
02-random-29 AC 69 ms 384 KB
02-random-30 AC 46 ms 384 KB
02-random-31 AC 99 ms 428 KB
02-random-32 AC 26 ms 384 KB
02-random-33 AC 54 ms 416 KB
02-random-34 AC 12 ms 384 KB
02-random-35 AC 80 ms 412 KB
02-random-36 AC 15 ms 384 KB
02-random-37 AC 57 ms 412 KB
02-random-38 AC 12 ms 384 KB
02-random-39 AC 121 ms 424 KB
02-random-40 AC 50 ms 428 KB
02-random-41 AC 35 ms 256 KB
02-random-42 AC 86 ms 420 KB
02-random-43 AC 118 ms 420 KB
02-random-44 AC 98 ms 428 KB
02-random-45 AC 124 ms 428 KB
02-random-46 AC 76 ms 408 KB
02-random-47 AC 23 ms 384 KB
02-random-48 AC 118 ms 420 KB
02-random-49 AC 117 ms 424 KB
03-killer-00 AC 13 ms 384 KB
03-killer-01 AC 13 ms 384 KB
03-killer-02 AC 10 ms 384 KB