cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: ABC157-F Yakiniku Optimization Problem
(Test/AtCoder/abc157_f.test.cpp)

二分探索を考える。 $t$ 秒で $K$ 枚の焼肉を焼くことができる領域には必ず(その $K$ 枚のうちの) $2$ 枚の焼肉が $t$ 秒ぴったりで焼けるような点が存在する。

そのような点は 中心が焼肉の位置、 半径が $\frac{t}{c}$ である円の交点である。

ある円が片方の円を内包する場合に注意 (焼肉の位置ぴったりに熱源を置いた場合も考慮すること)

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc157/tasks/abc157_f"
#define ERROR 0.000001

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Utility/BinarySearch.hpp"
#include "../../Src/GeometryR2/Point.hpp"
#include "../../Src/GeometryR2/Circle.hpp"
#include "../../Src/GeometryR2/Intersect/CircleAndCircle.hpp"
#include "../../Src/GeometryR2/CrossPoint/CircleAndCircle.hpp"
#include "../../Src/GeometryR2/Contain/CircleContainsPoint.hpp"

using namespace zawa;
using namespace geometryR2;

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    SetFastIO();
    SetPrecision(8);
    int n, k; std::cin >> n >> k;
    std::vector<Point> p(n);
    std::vector<Real> c(n);
    for (int i{} ; i < n ; i++) {
        std::cin >> p[i] >> c[i];
    }

    if (k == 1) {
        std::cout << 0 << '\n';
        return 0;
    }

    auto f{[&](Real t) -> bool {
        std::vector<Circle> circles(n);
        for (int i{} ; i < n ; i++) {
            circles[i] = Circle{p[i], t / c[i]};
        }
        std::vector<Point> cand{p};
        for (int i{} ; i < n ; i++) for (int j{i + 1} ; j < n ; j++) {
            if (!Intersect(circles[i], circles[j])) continue;
            auto v{CrossPoint(circles[i], circles[j])};
            cand.push_back(v.first);
            cand.push_back(v.second);
        }
        int max{};
        for (const auto& v : cand) {
            int cnt{};
            for (const auto& circle : circles) {
                cnt += CircleContainsPoint(circle, v) != OUTSIDE;
            }
            max = std::max(max, cnt);
        }
        return max >= k;
    }};

    Real ans{BinarySearch(Real{4000 * 100}, Real{}, f, 80)};
    std::cout << ans << '\n';
}
#line 1 "Test/AtCoder/abc157_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc157/tasks/abc157_f"
#define ERROR 0.000001

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Utility/BinarySearch.hpp"

#line 4 "Src/Utility/BinarySearch.hpp"

#include <cmath>
#include <functional>
#include <type_traits>
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
#line 2 "Src/GeometryR2/Point.hpp"

#line 2 "Src/GeometryR2/Real.hpp"

#line 4 "Src/GeometryR2/Real.hpp"

#line 6 "Src/GeometryR2/Real.hpp"
#include <cassert>

namespace zawa {

namespace geometryR2 {

using Real = long double;

namespace internal {

Real EPS{1e-12};
constexpr i32 negative{-1};
constexpr i32 zero{};
constexpr i32 positive{1};

} // namespace internal

Real& Eps() {
    return internal::EPS;
}

i32 Sign(Real value) {
    if (value < -Eps()) return internal::negative;
    if (value > Eps()) return internal::positive;
    return internal::zero;
}

bool Zero(Real value) {
    return Sign(value) == internal::zero;
}

bool Positive(Real value) {
    return Sign(value) == internal::positive;
}

bool Negative(Real value) {
    return Sign(value) == internal::negative;
}

bool Equal(Real a, Real b) {
    return Zero(a - b);
}

bool Smaller(Real a, Real b) {
    return Negative(a - b);
}

bool Bigger(Real a, Real b) {
    return Positive(a - b);
}

Real Square(Real value) {
    return (Zero(value) ? value : value * value);
}

Real Sqrt(Real value) {
    assert(!Negative(value));
    return (Zero(value) ? value : sqrtl(value));
}

Real Abs(Real value) {
    return (Negative(value) ? -value : value);
}

} // namespace geometryR2
 
} // namespace zawa
#line 2 "Src/GeometryR2/Angle.hpp"

#line 4 "Src/GeometryR2/Angle.hpp"

#line 6 "Src/GeometryR2/Angle.hpp"

namespace zawa {

namespace geometryR2 {

constexpr Real PI{acosl(-1)};
constexpr Real TAU{static_cast<Real>(2) * PI};

constexpr Real ArcToRadian(Real arc) {
    return (arc * PI) / static_cast<Real>(180);
}

constexpr Real RadianToArc(Real radian) {
    return (radian * static_cast<Real>(180)) / PI;
}

} // namespace geometryR2

} // namespace zawa
#line 5 "Src/GeometryR2/Point.hpp"

#line 9 "Src/GeometryR2/Point.hpp"

namespace zawa {

namespace geometryR2 {

class Point {
private:
    Real x_{}, y_{};
public:
    /* constructor */
    Point() = default;
    Point(Real x, Real y) : x_{x}, y_{y} {}

    /* getter, setter */
    Real x() const {
        return x_;
    }
    Real& x() {
        return x_;
    }
    Real y() const {
        return y_;
    }
    Real& y() {
        return y_;
    }

    /* operator */
    Point& operator+=(const Point& rhs) {
        x_ += rhs.x();
        y_ += rhs.y();
        return *this;
    }
    friend Point operator+(const Point& lhs, const Point& rhs) {
        return Point{lhs} += rhs;
    }
    Point operator+() const {
        return *this;
    }
    Point& operator-=(const Point& rhs) {
        x_ -= rhs.x();
        y_ -= rhs.y();
        return *this;
    }
    friend Point operator-(const Point& lhs, const Point& rhs) {
        return Point{lhs} -= rhs;
    }
    Point operator-() const {
        return Point{} - *this;
    }
    Point& operator*=(Real k) {
        x_ *= k;
        y_ *= k;
        return *this;
    }
    friend Point operator*(Real k, const Point& p) {
        return Point{p} *= k;
    }
    friend Point operator*(const Point& p, Real k) {
        return Point{p} *= k;
    }
    Point& operator/=(Real k) {
        assert(!Zero(k));
        x_ /= k;
        y_ /= k;
        return *this;
    }
    friend Point operator/(Real k, const Point& p) {
        return Point{p} /= k;
    }
    friend Point operator/(const Point& p, Real k) {
        return Point{p} /= k;
    }
    friend bool operator==(const Point& lhs, const Point& rhs) {
        return Equal(lhs.x(), rhs.x()) and Equal(lhs.y(), rhs.y());
    }
    friend bool operator!=(const Point& lhs, const Point& rhs) {
        return !Equal(lhs.x(), rhs.x()) or !Equal(lhs.y(), rhs.y());
    }
    friend bool operator<(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.x(), rhs.x()) or 
            (Equal(lhs.x(), rhs.x()) and Smaller(lhs.y(), rhs.y()));
    }
    friend bool operator<=(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.x(), rhs.x()) or 
            (Equal(lhs.x(), rhs.x()) and (Smaller(lhs.y(), rhs.y()) or Equal(lhs.y(), rhs.y())));
    }
    friend bool operator>(const Point& lhs, const Point& rhs) {
        return Bigger(lhs.x(), rhs.x()) or
            (Equal(lhs.x(), rhs.x()) and Bigger(lhs.y(), rhs.y()));
    }
    friend bool operator>=(const Point& lhs, const Point& rhs) {
        return Bigger(lhs.x(), rhs.x()) or
            (Equal(lhs.x(), rhs.x()) and (Bigger(lhs.y(), rhs.y()) or Equal(lhs.y(), rhs.y())));
    }
    friend std::istream& operator>>(std::istream& is, Point& p) {
        is >> p.x_ >> p.y_;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const Point& p) {
        os << '(' << p.x_ << ',' << p.y_ << ')';
        return os;
    }
    
    /* member function */
    Real normSquare() const {
        return Square(x_) + Square(y_);
    }
    Real norm() const {
        return Sqrt(normSquare());
    }
    void normalize() {
        assert((*this) != Point{});
        (*this) /= norm(); 
    }
    Point normalized() const {
        Point res{*this};
        res.normalize();
        return res;
    }
    Point rotated(Real radian) const {
        return Point{
            x_ * cosl(radian) - y_ * sinl(radian),
            x_ * sinl(radian) + y_ * cosl(radian)
        };
    }
    void rotate(Real radian) {
        *this = rotated(radian); 
    }
    Point rotatedByArc(Real arc) const {
        return rotated(ArcToRadian(arc));
    }
    void rotateByArc(Real arc) {
        *this = rotatedByArc(arc);
    }
    Real argument() const {
        return (Negative(y_) ? TAU : static_cast<Real>(0)) + atan2l(y_, x_);
    }
    Real argumentByArc() const {
        return RadianToArc(argument());
    }

    /* friend function */
    friend Real Dot(const Point& lhs, const Point& rhs) {
        return lhs.x() * rhs.x() + lhs.y() * rhs.y();
    }
    friend Real Cross(const Point& lhs, const Point& rhs) {
        return lhs.x() * rhs.y() - lhs.y() * rhs.x();
    }
    friend Real Argument(const Point& lhs, const Point& rhs) {
        return rhs.argument() - lhs.argument();
    }
    friend bool ArgComp(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.argument(), rhs.argument());
    }
};

using Vector = Point;

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Circle.hpp"

#line 2 "Src/GeometryR2/Distance/PointAndPoint.hpp"

#line 4 "Src/GeometryR2/Distance/PointAndPoint.hpp"

namespace zawa {

namespace geometryR2 {

Real Distance(const Point& p0, const Point& p1) {
    return Point{p1 - p0}.norm();
}

Real DistanceSquare(const Point& p0, const Point& p1) {
    return Point{p1 - p0}.normSquare();
}

} // namespace geometryR2

} // namespace zawa
#line 7 "Src/GeometryR2/Circle.hpp"

#line 10 "Src/GeometryR2/Circle.hpp"

namespace zawa {

namespace geometryR2 {

class Circle {
private:
    Point center_{};
    Real radius_{};
public:
    /* constructor */
    Circle() = default;
    Circle(const Point& center, Real radius) : center_{center}, radius_{radius} {
        assert(!Negative(radius));
    }
    Circle(Real x, Real y, Real r) : center_{x, y}, radius_{r} {
        assert(!Negative(r));
    }

    /* getter setter */
    const Point& center() const {
        return center_;
    }
    Point& center() {
        return center_;
    }
    Real radius() const {
        return radius_;
    }
    Real& radius() {
        return radius_;
    }

    /* operator */
    friend bool operator==(const Circle& lhs, const Circle& rhs) {
        return lhs.center() == rhs.center() and Equal(lhs.radius(), rhs.radius());
    }
    friend bool operator!=(const Circle& lhs, const Circle& rhs) {
        return lhs.center() != rhs.center() or !Equal(lhs.radius(), rhs.radius());
    }

    /* friend function */
    friend u32 NumberCommonTangent(const Circle& c0, const Circle& c1) {
        Real dist{DistanceSquare(c0.center(), c1.center())};
        Real down{Square(Abs(c0.radius() - c1.radius()))};
        if (Smaller(dist, down)) return 0;
        if (Equal(dist, down)) return 1;
        Real up{Square(c0.radius() + c1.radius())};
        if (Smaller(dist, up)) return 2;
        if (Equal(dist, up)) return 3;
        return 4;
    }
};

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Intersect/CircleAndCircle.hpp"

#line 5 "Src/GeometryR2/Intersect/CircleAndCircle.hpp"

namespace zawa {

namespace geometryR2 {

bool Intersect(const Circle& c0, const Circle& c1) {
    u32 number{NumberCommonTangent(c0, c1)};
    return 0u < number and number < 4u;
}

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/CrossPoint/CircleAndCircle.hpp"

#line 5 "Src/GeometryR2/CrossPoint/CircleAndCircle.hpp"

#line 7 "Src/GeometryR2/CrossPoint/CircleAndCircle.hpp"

namespace zawa {

namespace geometryR2 {

std::pair<Point, Point> CrossPoint(const Circle& lhs, const Circle& rhs) {
    assert(lhs.center() != rhs.center());
    assert(Intersect(lhs, rhs));
    assert(!Zero(lhs.radius()) or !Zero(rhs.radius()));
    if (Zero(lhs.radius())) return {lhs.center(), lhs.center()};
    if (Zero(rhs.radius())) return {rhs.center(), rhs.center()};
    Real d{Distance(lhs.center(), rhs.center())};
    Real cosine{(Square(lhs.radius()) + Square(d) - Square(rhs.radius()))
        / (static_cast<Real>(2)*lhs.radius()*d)};
    Real rc{lhs.radius()*cosine};
    Real rs{Sqrt(Square(lhs.radius()) - Square(rc))};
    Vector lr{Vector{rhs.center() - lhs.center()}.normalized()};
    Vector h{lhs.center() + lr*rc};
    std::pair<Point, Point> res;
    res.first = h + lr.rotatedByArc(90) * rs;
    res.second = h + lr.rotatedByArc(-90) * rs;
    return res;
}

} // namespace geometryR2
    
} // namespace zawa
#line 2 "Src/GeometryR2/Contain/CircleContainsPoint.hpp"

#line 2 "Src/GeometryR2/Contain/State.hpp"

namespace zawa {

namespace geometryR2 {

enum ContainState {
    INSIDE,
    ONLINE,
    OUTSIDE
};

} // namespace geometryR2

} // namespace zawa
#line 8 "Src/GeometryR2/Contain/CircleContainsPoint.hpp"

namespace zawa {

namespace geometryR2 {

ContainState CircleContainsPoint(const Circle& circle, const Point& p) {
    Real dist{Distance(circle.center(), p)};
    if (Smaller(dist, circle.radius())) {
        return INSIDE;
    }
    else if (Equal(dist, circle.radius())) {
        return ONLINE;
    }
    else {
        return OUTSIDE;
    }
}

} // namespace geometryR2

} // namespace zawa
#line 11 "Test/AtCoder/abc157_f.test.cpp"

using namespace zawa;
using namespace geometryR2;

#include <algorithm>
#line 17 "Test/AtCoder/abc157_f.test.cpp"
#include <vector>

int main() {
    SetFastIO();
    SetPrecision(8);
    int n, k; std::cin >> n >> k;
    std::vector<Point> p(n);
    std::vector<Real> c(n);
    for (int i{} ; i < n ; i++) {
        std::cin >> p[i] >> c[i];
    }

    if (k == 1) {
        std::cout << 0 << '\n';
        return 0;
    }

    auto f{[&](Real t) -> bool {
        std::vector<Circle> circles(n);
        for (int i{} ; i < n ; i++) {
            circles[i] = Circle{p[i], t / c[i]};
        }
        std::vector<Point> cand{p};
        for (int i{} ; i < n ; i++) for (int j{i + 1} ; j < n ; j++) {
            if (!Intersect(circles[i], circles[j])) continue;
            auto v{CrossPoint(circles[i], circles[j])};
            cand.push_back(v.first);
            cand.push_back(v.second);
        }
        int max{};
        for (const auto& v : cand) {
            int cnt{};
            for (const auto& circle : circles) {
                cnt += CircleContainsPoint(circle, v) != OUTSIDE;
            }
            max = std::max(max, cnt);
        }
        return max >= k;
    }};

    Real ans{BinarySearch(Real{4000 * 100}, Real{}, f, 80)};
    std::cout << ans << '\n';
}
Back to top page