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

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/abc422/tasks/abc422_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 422 E - Colinear
 * https://atcoder.jp/contests/jsc2025advance-final/submissions/69185007
 */

#include "../../Src/GeometryZ2/Contain/LineContainsPoint.hpp"
using namespace zawa::geometryZ2;
using namespace std;

#include <iostream>
#include <random>

int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N;
    cin >> N;
    vector<Point> P(N);
    for (auto& p : P)
        cin >> p;
    mt19937 mt{random_device{}()};
    for (int _ = 0 ; _ < 100 ; _++) {
        int p = 0, q = 0;
        while (p == q) {
            p = mt() % N;
            q = mt() % N;
        }
        Line l{P[p], P[q]};
        int cnt = 0;
        for (const Point& v : P)
            cnt += LineContainsPoint(l, v) == ONLINE;
        if (2 * cnt > N) {
            auto [a, b, c] = l.normalForm();
            cout << "Yes\n" << a << ' ' << b << ' ' << c << '\n';
            return 0;
        }
    }
    cout << "No\n";
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc422_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc422/tasks/abc422_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 422 E - Colinear
 * https://atcoder.jp/contests/jsc2025advance-final/submissions/69185007
 */

#line 2 "Src/GeometryZ2/Contain/LineContainsPoint.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 2 "Src/GeometryZ2/Line.hpp"

#line 2 "Src/GeometryZ2/Zahlen.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/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 2 "Src/GeometryZ2/Point.hpp"

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

#include <algorithm>
#include <iostream>
#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 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/Line.hpp"

#line 8 "Src/GeometryZ2/Line.hpp"
#include <tuple>

namespace zawa {

namespace geometryZ2 {

class Line {
private:
    Point p0_{}, p1_{};

public:
    /* constructor */
    Line() = default;
    Line(const Point& p0, const Point& p1) : p0_{p0}, p1_{p1} {}
    // y = ax + b
    Line(const Zahlen& a, const Zahlen& b) : p0_{Zahlen{}, b}, p1_{a, a + b} {}
    Line(const Line& l) : p0_{l.p0()}, p1_{l.p1()} {}

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

    /* operator */
    friend bool operator==(const Line& l0, const Line& l1) {
        return Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l1.p0())) 
            and Zero(Cross(l1.p0() - l0.p0(), l0.p1() - l0.p0()));
    }
    friend bool operator!=(const Line& l0, const Line& l1) {
        return !(l0 == l1);
    }
    friend bool operator<(const Line& l0, const Line& l1) {
        if (Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l1.p0()))) {
            return Relation(l0.p0(), l0.p1(), l1.p0()) == COUNTER_CLOCKWISE;
        }
        else {
            return Point::ArgComp(l0.positiveDir(), l1.positiveDir());
        }
    }
    friend bool operator<=(const Line& l0, const Line& l1) {
        return (l0 == l1) or (l0 < l1);
    }
    friend bool operator>(const Line& l0, const Line& l1) {
        if (Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l1.p0()))) {
            return Relation(l0.p0(), l0.p1(), l1.p0()) == CLOCKWISE;
        }
        else {
            return Point::ArgComp(l0.positiveDir(), l1.positiveDir());
        }
    }
    friend bool operator>=(const Line& l0, const Line& l1) {
        return (l0 == l1) or (l0 > l1);
    }

    /* member function */
    bool valid() const {
        return p0_ != p1_;
    }
    Vector positiveDir() const {
        Vector res{p1_ - p0_};
        if (Negative(res.x())) {
            res.x() *= -1;
            res.y() *= -1;
        }
        return res;
    }
    std::tuple<Zahlen, Zahlen, Zahlen> normalForm() const {
        Zahlen a = p0_.y() - p1_.y();
        Zahlen b = p1_.x() - p0_.x();
        Zahlen c = -a * p0_.x() - b * p0_.y();
        return {a, b, c};
    }
};

} // namespace geometryZ2

} // namespace zawa

#line 6 "Src/GeometryZ2/Contain/LineContainsPoint.hpp"

namespace zawa {

namespace geometryZ2 {

ContainState LineContainsPoint(const Line& l, const Point& p) {
    return Cross(p - l.p0(), l.p1() - l.p0()) == 0 ? ONLINE : OUTSIDE;
}

} // namespace geometryZ2

} // namespace zawa
#line 10 "Test/AtCoder/abc422_e.test.cpp"
using namespace zawa::geometryZ2;
using namespace std;

#line 14 "Test/AtCoder/abc422_e.test.cpp"
#include <random>

int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N;
    cin >> N;
    vector<Point> P(N);
    for (auto& p : P)
        cin >> p;
    mt19937 mt{random_device{}()};
    for (int _ = 0 ; _ < 100 ; _++) {
        int p = 0, q = 0;
        while (p == q) {
            p = mt() % N;
            q = mt() % N;
        }
        Line l{P[p], P[q]};
        int cnt = 0;
        for (const Point& v : P)
            cnt += LineContainsPoint(l, v) == ONLINE;
        if (2 * cnt > N) {
            auto [a, b, c] = l.normalForm();
            cout << "Yes\n" << a << ' ' << b << ' ' << c << '\n';
            return 0;
        }
    }
    cout << "No\n";
#else
    cout << "Hello World\n";
#endif
}
Back to top page