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/AOJ/1298.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1298"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/GeometryZ2/PointCloud.hpp"
#include "../../Src/GeometryZ2/Polygon.hpp"
#include "../../Src/GeometryZ2/Relation.hpp"
#include "../../Src/GeometryZ2/Intersect/PolygonAndPolygon.hpp"
#include "../../Src/GeometryZ2/Contain/ConvexPolygonContainsPoint.hpp"
#include "../../Src/GeometryZ2/ConvexHull.hpp"

bool solve() {
    using namespace zawa::geometryZ2;
    int n, m; std::cin >> n >> m;
    if (n == 0 and m == 0) return false;
    PointCloud p(n), q(m);
    for (auto& v : p) std::cin >> v;
    for (auto& v : q) std::cin >> v;
    if (n == 1 and m == 1) {
        std::cout << "YES" << '\n';
    }
    else if (n == 1 or m == 1) {
        if (n == 1) {
            std::swap(n, m);
            std::swap(p, q);
        }
        auto h1{ConvexHull<true>(p)};
        if (h1.size() == 2u) {
            std::cout << (Relation(h1[0], q[0], h1[1]) != ONLINE_FRONT ? "YES" : "NO") << '\n';
        }
        else {
            std::cout << (ConvexPolygonContainsPoint(h1, q[0]) == OUTSIDE ? "YES" : "NO") << '\n';
        }
    }
    else {
        auto h1{ConvexHull<true>(p)}, h2{ConvexHull<true>(q)};
        if (h1.size() == 2u and h2.size() == 2u) {
            std::cout << (Intersect(Segment{h1[0],h1[1]}, Segment{h2[0],h2[1]}) ? "NO" : "YES") << '\n';
        }
        else if (h1.size() == 2u or h2.size() == 2u) {
            if (h1.size() == 2u) std::swap(h1, h2);
            bool ok{true};
            ok &= ConvexPolygonContainsPoint(h1, h1[0]) == OUTSIDE;
            ok &= ConvexPolygonContainsPoint(h1, h2[1]) == OUTSIDE;
            for (size_t i{} ; i < h1.size() ; i++) {
                ok &= !Intersect(Segment{h1[i], h1[(i+1)%h1.size()]}, Segment{h2[0],h2[1]});
            }
            std::cout << (ok ? "YES" : "NO") << '\n';
        }
        else {
            bool ok{true};
            for (int i{} ; i < (int)h1.size() ; i++) {
                ok &= ConvexPolygonContainsPoint(h2, h1[i]) == OUTSIDE;
            }
            for (int i{} ; i < (int)h2.size() ; i++) {
                ok &= ConvexPolygonContainsPoint(h1, h2[i]) == OUTSIDE;
            }
            ok &= !Intersect(h1, h2);
            std::cout << (ok ? "YES" : "NO") << '\n';
        }
    }
    return true;
}

int main() {
    using namespace zawa;
    SetFastIO();
    while (solve()) ;
}
#line 1 "Test/AOJ/1298.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1298"

#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/GeometryZ2/PointCloud.hpp"

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

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

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

#include <cassert>

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 5 "Src/GeometryZ2/Point.hpp"

#include <algorithm>
#line 9 "Src/GeometryZ2/Point.hpp"
#include <limits>

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 4 "Src/GeometryZ2/PointCloud.hpp"

#line 6 "Src/GeometryZ2/PointCloud.hpp"
#include <vector>

namespace zawa {

namespace geometryZ2 {

using PointCloud = std::vector<Point>;

void ArgSort(PointCloud& p) {
    std::sort(p.begin(), p.end(), Point::ArgComp);
}

} // namespace geometryZ2 

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

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

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

namespace zawa {

namespace geometryZ2 {

enum RELATION {
    // p0 -> p1 -> p2の順で直線上に並んでいる
    ONLINE_FRONT        = -2,
    // (p1 - p0) -> (p2 - p0)が時計回りになっている
    CLOCKWISE           = -1,
    // p0 -> p2 -> p1の順で直線上に並んでいる
    ON_SEGMENT          =  0,
    // (p1 - p0) -> (p2 - p0)が反時計回りになっている
    COUNTER_CLOCKWISE   = +1,
    // p2 -> p0 -> p1、またはp1 -> p0 -> p2の順で直線上に並んでいる
    ONLINE_BACK         = +2
};

RELATION Relation(const Point& p0, const Point& p1, const Point& p2) {
    Point a{p1 - p0}, b{p2 - p0};
    if (Positive(Cross(a, b))) return COUNTER_CLOCKWISE;
    if (Negative(Cross(a, b))) return CLOCKWISE;
    if (Negative(Dot(a, b))) return ONLINE_BACK;
    if (a.normSquare() < b.normSquare()) return ONLINE_FRONT;
    return ON_SEGMENT;
};

} // namespace geometryZ2

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

#line 9 "Src/GeometryZ2/Polygon.hpp"
#include <iterator>
#include <type_traits>
#line 12 "Src/GeometryZ2/Polygon.hpp"

namespace zawa {

namespace geometryZ2 {

class Polygon {
private:
    std::vector<Point> data_;
public:
    usize size() const {
        return data_.size(); 
    }

    /* constructor */
    Polygon() = default;
    Polygon(const Polygon& polygon) : data_{polygon.data_} {}
    Polygon(const std::vector<Point>& data) : data_{data} {}
    Polygon(usize n) : data_{n} {
        assert(n >= static_cast<usize>(3));
    }

    /* operator */
    Polygon& operator=(const Polygon& polygon) {
        data_ = polygon.data_;
        return *this;
    }
    Point& operator[](usize i) {
        assert(i < size());
        return data_[i];
    }
    const Point& operator[](usize i) const {
        assert(i < size());
        return data_[i];
    }
    friend std::istream& operator>>(std::istream& is, Polygon& polygon) {
        for (size_t i{} ; i < polygon.size() ; i++) {
            is >> polygon[i];
        }
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const Polygon& polygon) {
        for (usize i{} ; i < polygon.size() ; i++) {
            std::cout << polygon[i] << (i + 1 == polygon.size() ? "" : " ");
        }
        return os;
    }

    /* member function */
    void reserve(usize n) {
        data_.reserve(n);
    }
    void pushBack(const Point& p) {
        data_.push_back(p);
    }
    void emplaceBack(Zahlen x, Zahlen y) {
        data_.emplace_back(x, y);
    }
    template <class RandomAccessIterator>
    void insert(usize n, RandomAccessIterator first, RandomAccessIterator last) {
        assert(n <= size());
        data_.insert(std::next(data_.begin(), n), first, last);
    }
    void orderRotate(usize i) {
        assert(i < size());
        std::rotate(data_.begin(), data_.begin() + i, data_.end());
    }
    template <class F>
    void normalForm(const F& func) {
        auto index{std::distance(data_.begin(), std::min_element(data_.begin(), data_.end(), func))};
        orderRotate(index);
    }
    void normalForm() {
        auto index{std::distance(data_.begin(), std::min_element(data_.begin(), data_.end()))};
        orderRotate(index);
    }
    template <class F>
    Polygon normalFormed(const F& func = [](const Point& a, const Point& b) -> bool { return a < b; }) const {
        Polygon res{*this};
        res.normalForm(func);
        return res;
    }
    Polygon normalFormed() {
        Polygon res{*this};
        res.normalForm();
        return res;
    }
    bool isConvex() const {
        assert(size() >= static_cast<usize>(3));
        for (usize i{} ; i < size() ; i++) {
            if (Relation(data_[i], data_[i+1==size()?0:i+1], data_[i+2>=size()?i+2-size():i+2])
                    == CLOCKWISE) {
                return false;
            }
        }
        return true;
    }
    Zahlen areaTwice() const {
        assert(size() >= static_cast<usize>(3));
        Zahlen res{};
        for (usize i{1} ; i < size() ; i++) {
            res += Cross(data_[i] - data_[0], data_[i+1==size()?0:i+1] - data_[0]);
        }
        return res;
    }
    Polygon subtriangle(usize i, usize j, usize k) const {
        assert(i < size());
        assert(j < size());
        assert(k < size());
        return Polygon{std::vector<Point>{ data_[i], data_[j], data_[k] }};
    }
};

}

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

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

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

namespace zawa {

namespace geometryZ2 {

class Segment {
private:
    Point p0_{}, p1_{};
public:
    /* constructor */
    Segment() = default;
    Segment(const Segment& s) : p0_{s.p0_}, p1_{s.p1_} {}
    Segment(const Point& p0, const Point& p1) : p0_{p0}, p1_{p1} {}

    /* getter, setter */ 
    const Point& p0() const {
        return p0_;
    }
    Point& p0() {
        return p0_;
    }
    const Point& p1() const {
        return p1_;
    }
    Point& p1() {
        return p1_;
    }

    /* operator */
    Segment& operator=(const Segment& s) {
        p0_ = s.p0();
        p1_ = s.p1();
        return *this;
    }
    friend bool operator==(const Segment& s0, const Segment& s1) {
        return (s0.p0() == s1.p0() and s0.p1() == s1.p1())
            or (s0.p1() == s1.p1() and s0.p1() == s1.p0());
    }
    friend bool operator!=(const Segment& s0, const Segment& s1) {
        return !(s0 == s1);
    }

    /* member function */
    bool valid() const {
        return p0_ != p1_;
    }
    bool straddle(const Segment& s) const {
        return Relation(p0_, p1_, s.p0()) * Relation(p0_, p1_, s.p1()) <= 0;
    }
};

} // namespace geometryZ2

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

#line 5 "Src/GeometryZ2/Intersect/SegmentAndSegment.hpp"

namespace zawa {

namespace geometryZ2 {

bool Intersect(const Segment& s0, const Segment& s1) {
    assert(s0.valid());
    assert(s1.valid());
    return s0.straddle(s1) and s1.straddle(s0);
}

} // namespace geometryZ2

} // namespace zawa
#line 6 "Src/GeometryZ2/Intersect/PolygonAndPolygon.hpp"

#line 8 "Src/GeometryZ2/Intersect/PolygonAndPolygon.hpp"

namespace zawa {

namespace geometryZ2 {

// !!!!!! naive algorithm !!!!!!
bool Intersect(const Polygon& p0, const Polygon& p1) {
    assert(p0.size() >= 2u);
    assert(p1.size() >= 2u);
    for (size_t i{} ; i < p0.size() ; i++) {
        for (size_t j{} ; j + 1 < p1.size() ; j++) {
            Segment s0{p0[i], p0[i+1==p0.size()?0u:i+1]};
            Segment s1{p1[j], p1[j+1==p1.size()?0u:j+1]};
            if (Intersect(s0, s1)) return true;
        }
    }
    return false;
}

} // namespace geometryZ2

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

#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/Contain/State.hpp"

namespace zawa {

namespace geometryZ2 {

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

} // namespace geometryZ2

} // namespace zawa
#line 9 "Src/GeometryZ2/Contain/ConvexPolygonContainsPoint.hpp"

#line 11 "Src/GeometryZ2/Contain/ConvexPolygonContainsPoint.hpp"

namespace zawa {

namespace geometryZ2 {

namespace internal {

bool TriangleContainsPoint(const Point& p0, const Point& p1, const Point& p2, const Point& p) {
    Zahlen area{Abs(Cross(p1 - p0, p2 - p0))};
    Zahlen value{};
    value += Abs(Cross(p0 - p, p1 - p));
    value += Abs(Cross(p1 - p, p2 - p));
    value += Abs(Cross(p2 - p, p0 - p));
    return area == value;
}

} // namespace internal

// note: 凸多角形であることを確認してください。
// note: normal formにしておいてください
ContainState ConvexPolygonContainsPoint(const Polygon& polygon, const Point& p) {
    usize n{polygon.size()};
    assert(n >= static_cast<usize>(3));
    if (polygon[0] == p or polygon[1] == p or polygon[n - 1] == p) {
        return ONLINE;
    }
    if (Relation(polygon[0], polygon[1], p) == ON_SEGMENT) {
        return ONLINE;
    }
    if (Relation(polygon[0], polygon[n - 1], p) == ON_SEGMENT) {
        return ONLINE;
    }
    if (Zero(Cross(polygon[1] - polygon[0], p - polygon[0]))) {
        return OUTSIDE;
    }
    if (Zero(Cross(polygon[n - 1] - polygon[0], p - polygon[0]))) {
        return OUTSIDE;
    }
    if (!(Relation(polygon[0], polygon[1], p) == COUNTER_CLOCKWISE and Relation(polygon[0], p, polygon[n - 1]) == COUNTER_CLOCKWISE)) {
        return OUTSIDE;
    }

    auto f{[&](usize i) -> bool {
        return Relation(polygon[0], polygon[i], p) == COUNTER_CLOCKWISE;
    }};

    usize pos{BinarySearch(usize{0}, usize{n - 1}, f)};
    if (p == polygon[pos]) return ONLINE;
    if (p == polygon[pos + 1]) return ONLINE;
    if (Relation(polygon[pos], polygon[pos + 1], p) == ON_SEGMENT) return ONLINE;

    if (internal::TriangleContainsPoint(polygon[0], polygon[pos], polygon[pos + 1], p)) {
        return INSIDE;
    }
    else {
        return OUTSIDE;
    }
}

} // namespace geometryZ2

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

#line 7 "Src/GeometryZ2/ConvexHull.hpp"

#line 13 "Src/GeometryZ2/ConvexHull.hpp"

namespace zawa {

namespace geometryZ2 {

template <bool strictly>
Polygon ConvexHull(const PointCloud& p) {
    PointCloud cp{p};
    std::sort(cp.begin(), cp.end());
    cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    if (cp.size() <= 2u) {
        return Polygon{cp};
    }
    PointCloud lower;
    lower.reserve(p.size());
    for (auto it{cp.begin()} ; it != cp.end() ; it++) {
        lower.push_back(*it);
        while (lower.size() >= 3u) {
            if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == COUNTER_CLOCKWISE) {
                break;
            }
            if constexpr (!strictly) {
                if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == ONLINE_FRONT) {
                    break;
                }
            }
            std::swap(lower[lower.size() - 2], lower[lower.size() - 1]);
            lower.pop_back();
        }
    }
    PointCloud upper;
    upper.reserve(p.size());
    for (auto it{cp.rbegin()} ; it != cp.rend() ; it++) {
        upper.push_back(*it);
        while (upper.size() >= 3u) {
            if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == COUNTER_CLOCKWISE) {
                break;
            }
            if constexpr (!strictly) {
                if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == ONLINE_FRONT) {
                    break;
                }
            }
            std::swap(upper[upper.size() - 2], upper[upper.size() - 1]);
            upper.pop_back();
        }
    }

    Polygon res;
    res.reserve(lower.size() + upper.size() - 2);
    res.insert(res.size(), lower.begin(), lower.end());
    res.insert(res.size(), std::next(upper.begin()), std::prev(upper.end()));
    return res;
}

} // namespace geometryZ2

} // namespace zawa
#line 10 "Test/AOJ/1298.test.cpp"

bool solve() {
    using namespace zawa::geometryZ2;
    int n, m; std::cin >> n >> m;
    if (n == 0 and m == 0) return false;
    PointCloud p(n), q(m);
    for (auto& v : p) std::cin >> v;
    for (auto& v : q) std::cin >> v;
    if (n == 1 and m == 1) {
        std::cout << "YES" << '\n';
    }
    else if (n == 1 or m == 1) {
        if (n == 1) {
            std::swap(n, m);
            std::swap(p, q);
        }
        auto h1{ConvexHull<true>(p)};
        if (h1.size() == 2u) {
            std::cout << (Relation(h1[0], q[0], h1[1]) != ONLINE_FRONT ? "YES" : "NO") << '\n';
        }
        else {
            std::cout << (ConvexPolygonContainsPoint(h1, q[0]) == OUTSIDE ? "YES" : "NO") << '\n';
        }
    }
    else {
        auto h1{ConvexHull<true>(p)}, h2{ConvexHull<true>(q)};
        if (h1.size() == 2u and h2.size() == 2u) {
            std::cout << (Intersect(Segment{h1[0],h1[1]}, Segment{h2[0],h2[1]}) ? "NO" : "YES") << '\n';
        }
        else if (h1.size() == 2u or h2.size() == 2u) {
            if (h1.size() == 2u) std::swap(h1, h2);
            bool ok{true};
            ok &= ConvexPolygonContainsPoint(h1, h1[0]) == OUTSIDE;
            ok &= ConvexPolygonContainsPoint(h1, h2[1]) == OUTSIDE;
            for (size_t i{} ; i < h1.size() ; i++) {
                ok &= !Intersect(Segment{h1[i], h1[(i+1)%h1.size()]}, Segment{h2[0],h2[1]});
            }
            std::cout << (ok ? "YES" : "NO") << '\n';
        }
        else {
            bool ok{true};
            for (int i{} ; i < (int)h1.size() ; i++) {
                ok &= ConvexPolygonContainsPoint(h2, h1[i]) == OUTSIDE;
            }
            for (int i{} ; i < (int)h2.size() ; i++) {
                ok &= ConvexPolygonContainsPoint(h1, h2[i]) == OUTSIDE;
            }
            ok &= !Intersect(h1, h2);
            std::cout << (ok ? "YES" : "NO") << '\n';
        }
    }
    return true;
}

int main() {
    using namespace zawa;
    SetFastIO();
    while (solve()) ;
}
Back to top page