test/aoj/0323/main.ternary.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0323"
#define ERROR 0.001
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include "Mylib/Algorithm/ternary_search_upwards.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
auto [x, r] = hl::input_tuple_vector<int64_t, int64_t>(N);
std::vector<std::pair<int64_t, int>> p;
for (int i = 0; i < N; ++i) {
p.emplace_back(x[i] - r[i], -1);
p.emplace_back(x[i] + r[i], 1);
}
std::sort(p.begin(), p.end());
double left = 0, right = 0;
int c = 0;
for (auto &a : p) {
if (c == N) {
right = a.first;
}
c -= a.second;
if (c == N) {
left = a.first;
}
}
auto f =
[&](double p) {
double ret = 1e9;
for (int i = 0; i < N; ++i) {
double l = std::abs(x[i] - p);
ret = std::min(ret, std::sqrt(r[i] * r[i] - l * l));
}
return ret;
};
auto a = hl::ternary_search_upwards<double>(left, right, f);
std::cout << std::fixed << std::setprecision(12) << f(a) << std::endl;
return 0;
}
#line 1 "test/aoj/0323/main.ternary.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0323"
#define ERROR 0.001
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#line 2 "Mylib/Algorithm/ternary_search_upwards.cpp"
#include <functional>
namespace haar_lib {
template <typename T = double, typename Func = std::function<T(T)>>
T ternary_search_upwards(T lb, T ub, const Func &f, int LOOP_COUNT = 100) {
T t1 = 0, t2 = 0;
while (LOOP_COUNT--) {
t1 = lb + (ub - lb) / 3;
t2 = lb + (ub - lb) / 3 * 2;
if (f(t1) > f(t2)) {
ub = t2;
} else {
lb = t1;
}
}
return lb;
}
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#include <vector>
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 10 "test/aoj/0323/main.ternary.test.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
auto [x, r] = hl::input_tuple_vector<int64_t, int64_t>(N);
std::vector<std::pair<int64_t, int>> p;
for (int i = 0; i < N; ++i) {
p.emplace_back(x[i] - r[i], -1);
p.emplace_back(x[i] + r[i], 1);
}
std::sort(p.begin(), p.end());
double left = 0, right = 0;
int c = 0;
for (auto &a : p) {
if (c == N) {
right = a.first;
}
c -= a.second;
if (c == N) {
left = a.first;
}
}
auto f =
[&](double p) {
double ret = 1e9;
for (int i = 0; i < N; ++i) {
double l = std::abs(x[i] - p);
ret = std::min(ret, std::sqrt(r[i] * r[i] - l * l));
}
return ret;
};
auto a = hl::ternary_search_upwards<double>(left, right, f);
std::cout << std::fixed << std::setprecision(12) << f(a) << std::endl;
return 0;
}
Back to top page
Input tuple vector
(Mylib/IO/input_tuple_vector.cpp)