Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aizu-online-judge/1342.test.cpp
- View this file on GitHub
- Last update: 2020-12-08 15:39:54+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/problems/1342
Depends on
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1342"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include "src/opt/binary_search.hpp"
int main() {
using namespace std;
using namespace workspace;
static const double eps = 1e-9;
struct point {
double x, y;
double dist(point rhs) { return hypot(rhs.x - x, rhs.y - y); }
point normalized() { return {x / hypot(x, y), y / hypot(x, y)}; }
point scalized(double len) {
return {x / hypot(x, y) * len, y / hypot(x, y) * len};
}
point operator+(point rhs) { return {x + rhs.x, y + rhs.y}; }
bool operator==(point rhs) {
return abs(x - rhs.x) < eps and abs(y - rhs.y) < eps;
}
};
struct line {
double a, b, c;
};
struct circle {
point center;
double radius;
std::pair<point, point> intersect(circle rhs) {
double r1, r2;
auto [a, b] = center;
auto [c, d] = rhs.center;
r1 = radius;
r2 = rhs.radius;
if (a == c and b == d) return {center, center};
line cln{2 * (c - a), 2 * (d - b),
r1 * r1 - r2 * r2 + c * c + d * d - a * a - b * b};
return intersect(cln);
}
std::pair<point, point> intersect(line ln) {
point p1, p2;
auto [a, b, c] = ln;
double d = (c - a * center.x - b * center.y) / hypot(a, b);
if (abs(d) > radius) return make_pair(p1, p2);
point mid = center + point{a, b}.scalized(d);
d = sqrt(radius * radius - d * d);
p1 = mid + point{b, -a}.scalized(d);
p2 = mid + point{b, -a}.scalized(-d);
return make_pair(p1, p2);
}
};
struct stick {
point position;
double height;
};
int n;
double wall_hgt;
const double sqre = 100;
while (1) {
cin >> n;
cin >> wall_hgt;
if (!n) break;
vector<stick> stks(n);
for (auto &[p, h] : stks) {
double x, y;
cin >> x >> y >> h;
p = {x, y};
}
auto check_rad = [&](const double rad) -> bool {
vector<circle> crcls;
for (auto &[p, h] : stks) {
circle cir;
cir.center = p;
cir.radius = rad > h ? sqrt(rad * rad - (rad - h) * (rad - h)) : rad;
crcls.emplace_back(cir);
}
const double walld =
rad > wall_hgt ? sqrt(rad * rad - (rad - wall_hgt) * (rad - wall_hgt))
: rad;
auto check_external = [&](point p) -> bool {
for (auto [c, r] : crcls) {
if (p.dist(c) < r - eps) return false;
}
return min({p.x, sqre - p.x, p.y, sqre - p.y}) > walld - eps;
};
vector<point> cands;
// corner
for (auto x : {walld, sqre - walld}) {
for (auto y : {walld, sqre - walld}) {
cands.push_back({x, y});
}
}
// between circls
for (auto c1 : crcls) {
for (auto c2 : crcls) {
if (c1.center == c2.center) continue;
auto [p1, p2] = c1.intersect(c2);
cands.emplace_back(p1);
cands.emplace_back(p2);
}
}
// wall and circle
for (auto c : crcls) {
for (auto ln : vector<line>{{0, 1, walld},
{1, 0, walld},
{0, 1, sqre - walld},
{1, 0, sqre - walld}}) {
auto [p1, p2] = c.intersect(ln);
cands.emplace_back(p1);
cands.emplace_back(p2);
}
}
for (auto p : cands) {
if (check_external(p)) return true;
}
return false;
};
printf("%.5f\n", workspace::binary_search(0.0, 130.0, eps, check_rad));
}
}#line 1 "test/aizu-online-judge/1342.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1342"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#line 2 "src/opt/binary_search.hpp"
/*
* @file binary_search.hpp
* @brief Binary Search
*/
#include <cassert>
#include <limits>
#include <tuple>
#line 12 "src/opt/binary_search.hpp"
namespace workspace {
/*
* @fn binary_search
* @brief binary search on a discrete range.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param pred the predicate
* @return the closest point to (ng) where pred is true
*/
template <class Iter, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Iter>())),
bool>::value,
Iter>::type
binary_search(Iter ok, Iter ng, Pred pred) {
assert(ok != ng);
typename std::make_signed<decltype(ng - ok)>::type dist(ng - ok);
while (1 < dist || dist < -1) {
const Iter mid(ok + dist / 2);
if (pred(mid))
ok = mid, dist -= dist / 2;
else
ng = mid, dist /= 2;
}
return ok;
}
/*
* @fn binary_search
* @brief binary search on the real number line.
* @param ok pred(ok) is true
* @param ng pred(ng) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary point
*/
template <class Real, class Pred>
typename std::enable_if<
std::is_convertible<decltype(std::declval<Pred>()(std::declval<Real>())),
bool>::value,
Real>::type
binary_search(Real ok, Real ng, const Real eps, Pred pred) {
assert(ok != ng);
for (auto loops = 0; loops != std::numeric_limits<Real>::digits &&
(ok + eps < ng || ng + eps < ok);
++loops) {
const Real mid{(ok + ng) / 2};
(pred(mid) ? ok : ng) = mid;
}
return ok;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on discrete ranges.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param pred the predicate
* @return the closest points to (second) where pred is true
*/
template <class Array,
class Iter = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Iter>>())[0]),
bool>::value,
std::vector<Iter>>::type
parallel_binary_search(Array ends, Pred pred) {
std::vector<Iter> mids(std::size(ends));
for (;;) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Iter &ok = std::get<0>(ends[i]);
const Iter &ng = std::get<1>(ends[i]);
const Iter mid(
ok + typename std::make_signed<decltype(ng - ok)>::type(ng - ok) / 2);
if (mids[i] != mid) {
all_found = false;
mids[i] = mid;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
/*
* @fn parallel_binary_search
* @brief parallel binary search on the real number line.
* @param ends a vector of pairs; pred(first) is true, pred(second) is false
* @param eps the error tolerance
* @param pred the predicate
* @return the boundary points
*/
template <class Array,
class Real = typename std::decay<
decltype(std::get<0>(std::declval<Array>()[0]))>::type,
class Pred>
typename std::enable_if<
std::is_convertible<
decltype(std::declval<Pred>()(std::declval<std::vector<Real>>())[0]),
bool>::value,
std::vector<Real>>::type
parallel_binary_search(Array ends, const Real eps, Pred pred) {
std::vector<Real> mids(std::size(ends));
for (auto loops = 0; loops != std::numeric_limits<Real>::digits; ++loops) {
bool all_found = true;
for (size_t i{}; i != std::size(ends); ++i) {
const Real ok = std::get<0>(ends[i]);
const Real ng = std::get<1>(ends[i]);
if (ok + eps < ng || ng + eps < ok) {
all_found = false;
mids[i] = (ok + ng) / 2;
}
}
if (all_found) break;
const auto res = pred(mids);
for (size_t i{}; i != std::size(ends); ++i) {
(res[i] ? std::get<0>(ends[i]) : std::get<1>(ends[i])) = mids[i];
}
}
return mids;
}
} // namespace workspace
#line 10 "test/aizu-online-judge/1342.test.cpp"
int main() {
using namespace std;
using namespace workspace;
static const double eps = 1e-9;
struct point {
double x, y;
double dist(point rhs) { return hypot(rhs.x - x, rhs.y - y); }
point normalized() { return {x / hypot(x, y), y / hypot(x, y)}; }
point scalized(double len) {
return {x / hypot(x, y) * len, y / hypot(x, y) * len};
}
point operator+(point rhs) { return {x + rhs.x, y + rhs.y}; }
bool operator==(point rhs) {
return abs(x - rhs.x) < eps and abs(y - rhs.y) < eps;
}
};
struct line {
double a, b, c;
};
struct circle {
point center;
double radius;
std::pair<point, point> intersect(circle rhs) {
double r1, r2;
auto [a, b] = center;
auto [c, d] = rhs.center;
r1 = radius;
r2 = rhs.radius;
if (a == c and b == d) return {center, center};
line cln{2 * (c - a), 2 * (d - b),
r1 * r1 - r2 * r2 + c * c + d * d - a * a - b * b};
return intersect(cln);
}
std::pair<point, point> intersect(line ln) {
point p1, p2;
auto [a, b, c] = ln;
double d = (c - a * center.x - b * center.y) / hypot(a, b);
if (abs(d) > radius) return make_pair(p1, p2);
point mid = center + point{a, b}.scalized(d);
d = sqrt(radius * radius - d * d);
p1 = mid + point{b, -a}.scalized(d);
p2 = mid + point{b, -a}.scalized(-d);
return make_pair(p1, p2);
}
};
struct stick {
point position;
double height;
};
int n;
double wall_hgt;
const double sqre = 100;
while (1) {
cin >> n;
cin >> wall_hgt;
if (!n) break;
vector<stick> stks(n);
for (auto &[p, h] : stks) {
double x, y;
cin >> x >> y >> h;
p = {x, y};
}
auto check_rad = [&](const double rad) -> bool {
vector<circle> crcls;
for (auto &[p, h] : stks) {
circle cir;
cir.center = p;
cir.radius = rad > h ? sqrt(rad * rad - (rad - h) * (rad - h)) : rad;
crcls.emplace_back(cir);
}
const double walld =
rad > wall_hgt ? sqrt(rad * rad - (rad - wall_hgt) * (rad - wall_hgt))
: rad;
auto check_external = [&](point p) -> bool {
for (auto [c, r] : crcls) {
if (p.dist(c) < r - eps) return false;
}
return min({p.x, sqre - p.x, p.y, sqre - p.y}) > walld - eps;
};
vector<point> cands;
// corner
for (auto x : {walld, sqre - walld}) {
for (auto y : {walld, sqre - walld}) {
cands.push_back({x, y});
}
}
// between circls
for (auto c1 : crcls) {
for (auto c2 : crcls) {
if (c1.center == c2.center) continue;
auto [p1, p2] = c1.intersect(c2);
cands.emplace_back(p1);
cands.emplace_back(p2);
}
}
// wall and circle
for (auto c : crcls) {
for (auto ln : vector<line>{{0, 1, walld},
{1, 0, walld},
{0, 1, sqre - walld},
{1, 0, sqre - walld}}) {
auto [p1, p2] = c.intersect(ln);
cands.emplace_back(p1);
cands.emplace_back(p2);
}
}
for (auto p : cands) {
if (check_external(p)) return true;
}
return false;
};
printf("%.5f\n", workspace::binary_search(0.0, 130.0, eps, check_rad));
}
}