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: Test/AtCoder/abc191_d.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc191/tasks/abc191_d"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Template/FloatingNumberAlias.hpp"
#include "../../Src/Number/IntegerDivision.hpp"
#include "../../Src/Utility/FloatingMarkerShift.hpp"
#include "../../Src/Utility/BinarySearch.hpp"
#include "../../Src/GeometryZ2/Circle.hpp"
#include "../../Src/GeometryZ2/Contain/CircleContainsPoint.hpp"

#include <iostream>
#include <cmath>

using namespace zawa;
using namespace geometryZ2;

i64 parse() {
    std::string s; std::cin >> s;
    return FloatingMarkerShift(s, 4);
}

constexpr i64 mul{10000}, range{200100};

int main() {
    i64 X{parse()}, Y{parse()}, R{parse()}; 
    Circle c{Point{X, Y}, R};
    u64 ans{};
    
    auto contain{[&](Zahlen x, Zahlen y) -> bool {
        return CircleContainsPoint(c, Point{x, y}) != OUTSIDE;
    }};

    for (i64 x{-range * mul} ; x <= range * mul ; x += mul) {
        if (!contain(x, Y)) continue;
        i64 u{BinarySearch(Y, Y + R + 1, [&](i64 p) -> bool { return contain(x, p); })};
        u = DivFloor(u, mul);
        i64 d{BinarySearch(Y, Y - R - 1, [&](i64 p) -> bool { return contain(x, p); })};
        d = DivCeil(d, mul);
        ans += (u - d + 1);
    }
    std::cout << ans << std::endl;
}
#line 1 "Test/AtCoder/abc191_d.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc191/tasks/abc191_d"

#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 2 "Src/Template/FloatingNumberAlias.hpp"

namespace zawa {

using ld = long double;

} // namespace zawa
#line 2 "Src/Number/IntegerDivision.hpp"

#include <type_traits>
#include <cassert>

namespace zawa {

template <class T>
constexpr T DivFloor(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivFloor argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return a / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? a / b : (a - b + 1) / b);
    }
}

template <class T>
constexpr T DivCeil(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivCeil argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return (a + b - 1) / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? (a + b - 1) / b : a / b);
    }
}

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

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

#include <string>
#line 7 "Src/Utility/FloatingMarkerShift.hpp"
#include <limits>

namespace zawa {

i64 FloatingMarkerShift(const std::string& S, u32 shift) {
    static i64 lim10{std::numeric_limits<i64>::max() / 10};
    assert(not S.empty());
    i64 res{};
    u32 moved{};
    bool start{};
    bool minus{S[0] == '-'};
    for (u32 i{(u32)minus} ; i < S.size() ; i++) {
        if (S[i] == '.') {
            start = true;
        }
        else {
            if (start) moved++;
            assert(res < lim10);
            res = res * 10;
            assert(res < std::numeric_limits<i64>::max() - (S[i] - '0'));
            res += S[i] - '0';
        }
    }
    assert(moved <= shift);
    while (moved < shift) {
        moved++;
        assert(res < lim10);
        res = res * 10;
    }
    if (minus) res *= -1;
    return res;
}

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

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

#include <cmath>
#include <functional>
#line 8 "Src/Utility/BinarySearch.hpp"
#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/GeometryZ2/Circle.hpp"

#line 2 "Src/GeometryZ2/Zahlen.hpp"

#line 4 "Src/GeometryZ2/Zahlen.hpp"

#line 6 "Src/GeometryZ2/Zahlen.hpp"

namespace zawa {

namespace geometryZ2 {

using Zahlen = i64;

namespace internal {

constexpr i32 positive{1};
constexpr i32 zero{0};
constexpr i32 negative{-1};

} // namespace internal

constexpr i32 Sign(Zahlen value) {
    if (value < 0) return internal::negative;
    if (value > 0) return internal::positive;
    return internal::zero;
}

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

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

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

constexpr Zahlen Abs(Zahlen value) {
    return (value > 0 ? value : -value);
}

constexpr Zahlen Square(Zahlen value) {
    return value * value;
}

} // namespace geometryZ2

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

#line 5 "Src/GeometryZ2/Point.hpp"

#include <algorithm>
#include <iostream>
#line 10 "Src/GeometryZ2/Point.hpp"

namespace zawa {

namespace geometryZ2 {

class Point {
private:
    Zahlen x_{}, y_{};
    static constexpr i32 origin{0};
    static constexpr i32 firstQuadrant{1};
    static constexpr i32 secondQuadrant{2};
    static constexpr i32 thirdQuadrant{-2};
    static constexpr i32 forthQuadrant{-1};
public:
    /* constructor */
    Point() = default;
    Point(const Point& p) : x_{p.x()}, y_{p.y()} {}
    Point(Zahlen x, Zahlen y) : x_{x}, y_{y} {}

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

    /* operator */
    Point& operator=(const Point& p) {
        x() = p.x();
        y() = p.y();
        return *this;
    }
    Point& operator+=(const Point& p) {
        x() += p.x();
        y() += p.y();
        return *this;
    }
    friend Point operator+(const Point& p0, const Point& p1) {
        return Point{p0} += p1;
    }
    Point& operator-=(const Point& p) {
        x() -= p.x();
        y() -= p.y();
        return *this;
    }
    friend Point operator-(const Point& p0, const Point& p1) {
        return Point{p0} -= p1;
    }
    Point& operator*=(Zahlen k) {
        x() *= k;
        y() *= k;
        return *this;
    }
    friend Point operator*(const Point& p, Zahlen k) {
        return Point{p} *= k;
    }
    friend Point operator*(Zahlen k, const Point& p) {
        return Point{p} *= k;
    }
    Point& operator/=(Zahlen k) {
        assert(k);
        assert(x() % k == 0);
        assert(y() % k == 0);
        x() /= k;
        y() /= k;
        return *this;
    }
    friend Point operator/(const Point& p, Zahlen k) {
        return Point{p} /= k;
    }
    friend bool operator==(const Point& p0, const Point& p1) {
        return p0.x() == p1.x() and p0.y() == p1.y();
    }
    friend bool operator!=(const Point& p0, const Point& p1) {
        return p0.x() != p1.x() or p0.y() != p1.y();
    }
    friend bool operator<(const Point& p0, const Point& p1) {
        if (p0.x() != p1.x()) return p0.x() < p1.x();
        else return p0.y() < p1.y();
    }
    friend bool operator<=(const Point& p0, const Point& p1) {
        return (p0 < p1) or (p0 == p1);
    }
    friend bool operator>(const Point& p0, const Point& p1) {
        if (p0.x() != p1.x()) return p0.x() > p1.x();
        else return p0.y() > p1.y();
    }
    friend bool operator>=(const Point& p0, const Point& p1) {
        return (p0 > p1) or (p0 == p1);
    }
    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 */
    Zahlen normSquare() const {
        return Square(x()) + Square(y());
    }
    bool isNormSquareOver(Zahlen d) const {
        assert(!Negative(d));
        auto [mn, mx]{std::minmax({ Abs(x()), Abs(y()) })};
        if (mx and mx > d / mx) {
            return true;
        }
        long long s1{Square(mn)}, s2{Square(mx)};
        if (s1 > d - s2) {
            return true;
        }
        return false;
    }
    bool isNormSquareOverflow() const {
        return isNormSquareOver(std::numeric_limits<Zahlen>::max());
    }

    i32 area() const {
        if (x_ == 0 and y_ == 0) return origin;
        if (x_ <= 0 and y_ < 0) return thirdQuadrant;
        if (x_ > 0 and y_ <= 0) return forthQuadrant;
        if (x_ >= 0 and y_ > 0) return firstQuadrant;
        return secondQuadrant;
    }

    /* static member */
    static bool ArgComp(const Point& p0, const Point& p1) {
        if (p0.area() != p1.area()) return p0.area() < p1.area();
        Zahlen cross{Cross(p0, p1)};
        return (!Zero(cross) ? Positive(cross) : p0.normSquare() < p1.normSquare());
    }

    /* friend function */
    friend Zahlen Dot(const Point& p0, const Point& p1) {
        return p0.x() * p1.x() + p0.y() * p1.y();
    }
    friend Zahlen Cross(const Point& p0, const Point& p1) {
        return p0.x() * p1.y() - p0.y() * p1.x();
    }
};
using Vector = Point;

} // namespace geometryZ2

} // namespace zawa
#line 2 "Src/GeometryZ2/Distance/PointAndPoint.hpp"

#line 5 "Src/GeometryZ2/Distance/PointAndPoint.hpp"

namespace zawa {

namespace geometryZ2 {

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

} // namespace geometryZ2

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

#line 9 "Src/GeometryZ2/Circle.hpp"

namespace zawa {

namespace geometryZ2 {

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

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

    /* operator */
    Circle& operator=(const Circle& c) {
        radius_ = c.radius();
        center_ = c.center();
        return *this;
    }
    friend bool operator==(const Circle& c0, const Circle& c1) {
        return c0.radius() == c1.radius() and c0.center() == c1.center();
    }
    friend bool operator!=(const Circle& c0, const Circle& c1) {
        return c0.radius() != c1.radius() or c0.center() != c1.center();
    }

    /* member */
    
    Zahlen radiusSquare() const {
        return Square(radius_);
    }

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

} // namespace geometryZ2

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

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

namespace zawa {

namespace geometryZ2 {

enum ContainState {
    INSIDE          = 0,
    ONLINE          = 1,
    OUTSIDE         = 2
};

} // namespace geometryZ2

} // namespace zawa
#line 6 "Src/GeometryZ2/Contain/CircleContainsPoint.hpp"

namespace zawa {

namespace geometryZ2 {

ContainState CircleContainsPoint(const Circle& c, const Point& p) {
    Zahlen dist{DistanceSquare(c.center(), p)};
    if (dist < c.radiusSquare()) {
        return INSIDE;
    }
    else if (dist == c.radiusSquare()) {
        return ONLINE;
    }
    else {
        return OUTSIDE;
    }
}

} // namespace geometryZ2

} // namespace zawa
#line 10 "Test/AtCoder/abc191_d.test.cpp"

#line 13 "Test/AtCoder/abc191_d.test.cpp"

using namespace zawa;
using namespace geometryZ2;

i64 parse() {
    std::string s; std::cin >> s;
    return FloatingMarkerShift(s, 4);
}

constexpr i64 mul{10000}, range{200100};

int main() {
    i64 X{parse()}, Y{parse()}, R{parse()}; 
    Circle c{Point{X, Y}, R};
    u64 ans{};
    
    auto contain{[&](Zahlen x, Zahlen y) -> bool {
        return CircleContainsPoint(c, Point{x, y}) != OUTSIDE;
    }};

    for (i64 x{-range * mul} ; x <= range * mul ; x += mul) {
        if (!contain(x, Y)) continue;
        i64 u{BinarySearch(Y, Y + R + 1, [&](i64 p) -> bool { return contain(x, p); })};
        u = DivFloor(u, mul);
        i64 d{BinarySearch(Y, Y - R - 1, [&](i64 p) -> bool { return contain(x, p); })};
        d = DivCeil(d, mul);
        ans += (u - d + 1);
    }
    std::cout << ans << std::endl;
}
Back to top page