test/aoj/0323.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0323

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• 黄金分割探索 (src/Optimization/golden_search.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0323
// competitive-verifier: ERROR 0.00001
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <iomanip>
#include "src/Optimization/golden_search.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using R= long double;
 cout << fixed << setprecision(10);
 int N;
 cin >> N;
 int x[N], r[N];
 for (int i= 0; i < N; ++i) cin >> x[i] >> r[i];
 auto f= [&](R t) {
  R ret= 1e14;
  for (int i= 0; i < N; ++i) ret= min(ret, R(r[i]) * r[i] - R(t - x[i]) * (t - x[i]));
  return sqrt(ret);
 };
 int left= -1e7, right= 1e7;
 for (int i= 0; i < N; ++i) left= max(left, x[i] - r[i]), right= min(right, x[i] + r[i]);
 cout << golden_search<MAXIMIZE>(f, left, right).second << '\n';
 return 0;
}

#line 1 "test/aoj/0323.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0323
// competitive-verifier: ERROR 0.00001
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <iomanip>
#line 2 "src/Optimization/golden_search.hpp"
#include <cmath>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 6 "src/Optimization/golden_search.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<long double, result_type_t<F>> golden_search(const F &f, long double l, long double r, int iter= 100) {
 static constexpr long double c= 0.38196601125;
 assert(l <= r);
 long double x= l + (r - l) * c, y= r - (r - l) * c;
 result_type_t<F> fx= f(x), fy= f(y);
 for (bool g; iter--;) {
  if constexpr (obj == MINIMIZE) g= fx < fy;
  else g= fx > fy;
  if (g) r= y, y= x, fy= fx, fx= f(x= l + (r - l) * c);
  else l= x, x= y, fx= fy, fy= f(y= r - (r - l) * c);
 }
 return {x, fx};
}
#line 8 "test/aoj/0323.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using R= long double;
 cout << fixed << setprecision(10);
 int N;
 cin >> N;
 int x[N], r[N];
 for (int i= 0; i < N; ++i) cin >> x[i] >> r[i];
 auto f= [&](R t) {
  R ret= 1e14;
  for (int i= 0; i < N; ++i) ret= min(ret, R(r[i]) * r[i] - R(t - x[i]) * (t - x[i]));
  return sqrt(ret);
 };
 int left= -1e7, right= 1e7;
 for (int i= 0; i < N; ++i) left= max(left, x[i] - r[i]), right= min(right, x[i] + r[i]);
 cout << golden_search<MAXIMIZE>(f, left, right).second << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	00_sample_01.in	AC	4 ms	4 MB
g++-13	00_sample_02.in	AC	4 ms	4 MB
g++-13	01_shift10.in	AC	68 ms	5 MB
g++-13	01_shift_00.in	AC	68 ms	5 MB
g++-13	01_small_00.in	AC	4 ms	4 MB
g++-13	01_small_01.in	AC	4 ms	4 MB
g++-13	02_single_00.in	AC	4 ms	4 MB
g++-13	02_single_01.in	AC	4 ms	4 MB
g++-13	02_single_02.in	AC	4 ms	4 MB
g++-13	03_rand_00.in	AC	4 ms	4 MB
g++-13	03_rand_01.in	AC	4 ms	4 MB
g++-13	04_largerand_00.in	AC	9 ms	4 MB
g++-13	04_largerand_01.in	AC	10 ms	4 MB
g++-13	10_common_00.in	AC	68 ms	5 MB
g++-13	10_common_01.in	AC	68 ms	5 MB
g++-13	20_small_area_00.in	AC	68 ms	5 MB
g++-13	20_small_area_01.in	AC	68 ms	5 MB
g++-13	30_nest_center.in	AC	68 ms	5 MB
g++-13	30_nest_left.in	AC	68 ms	5 MB
g++-13	30_nest_right.in	AC	68 ms	5 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	4 ms	4 MB
clang++-18	00_sample_02.in	AC	4 ms	4 MB
clang++-18	01_shift10.in	AC	69 ms	5 MB
clang++-18	01_shift_00.in	AC	68 ms	5 MB
clang++-18	01_small_00.in	AC	4 ms	4 MB
clang++-18	01_small_01.in	AC	4 ms	4 MB
clang++-18	02_single_00.in	AC	4 ms	4 MB
clang++-18	02_single_01.in	AC	4 ms	4 MB
clang++-18	02_single_02.in	AC	4 ms	4 MB
clang++-18	03_rand_00.in	AC	4 ms	4 MB
clang++-18	03_rand_01.in	AC	4 ms	4 MB
clang++-18	04_largerand_00.in	AC	9 ms	4 MB
clang++-18	04_largerand_01.in	AC	11 ms	4 MB
clang++-18	10_common_00.in	AC	69 ms	5 MB
clang++-18	10_common_01.in	AC	69 ms	5 MB
clang++-18	20_small_area_00.in	AC	69 ms	5 MB
clang++-18	20_small_area_01.in	AC	69 ms	5 MB
clang++-18	30_nest_center.in	AC	68 ms	5 MB
clang++-18	30_nest_left.in	AC	68 ms	5 MB
clang++-18	30_nest_right.in	AC	68 ms	5 MB

Back to top page