#include #include using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; using mint = modint998244353; const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; const double EPS = 1e-18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } /** * @file point.hpp * @brief 二次元幾何の点 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/geometry/point.hpp */ #ifndef KWM_T_GEOMETRY_POINT_HPP #define KWM_T_GEOMETRY_POINT_HPP #include #include /** * @brief 2D integer point / vector * * 整数座標の2次元点(ベクトル)構造体。 * 幾何・格子問題で使用。 * * 典型用途: * ・cross / dot * ・偏角ソート * ・ベクトル演算 * * 使用例: * * Point a(1,2), b(3,4); * auto c = a + b; * long long cr = a.cross(b); * * verified: * ・https://atcoder.jp/contests/awc0079/submissions/76187291 */ namespace kwm_t::geometry { template struct Point { T x; T y; constexpr Point() : x(0), y(0) {} constexpr Point(T x, T y) : x(x), y(y) {} /* lexicographic order */ constexpr bool operator<(const Point& o) const { if (x != o.x) return x < o.x; return y < o.y; } constexpr bool operator==(const Point& o) const { return x == o.x && y == o.y; } constexpr bool operator!=(const Point& o) const { return !(*this == o); } /* vector operators */ constexpr Point operator+(const Point& o) const { return { x + o.x, y + o.y }; } constexpr Point operator-(const Point& o) const { return { x - o.x, y - o.y }; } constexpr Point operator*(T k) const { return { x * k, y * k }; } constexpr Point operator/(T k) const { return { x / k, y / k }; } /* inner / outer products */ auto dot(const Point& o) const { return x * o.x + y * o.y; } auto dist(const Point& o) const { return (x - o.x) * (x - o.x) + (y - o.y) * (y - o.y); } auto cross(const Point& o) const { return x * o.y - y * o.x; } /* squared norm */ auto norm2() const { return x * x + y * y; } /* rotate 90° counterclockwise */ constexpr Point rot90() const { return { -y, x }; } /* rotate 90° clockwise */ constexpr Point rot90_cw() const { return { y, -x }; } }; /** * 任意角回転(浮動小数用) */ template Point rotate(const Point& p, double rad) { double c = std::cos(rad); double s = std::sin(rad); return { p.x * c - p.y * s, p.x * s + p.y * c }; } /** * 偏角ソート comparator */ template bool polar_cmp(const Point& a, const Point& b) { bool ha = (a.y < 0 || (a.y == 0 && a.x < 0)); bool hb = (b.y < 0 || (b.y == 0 && b.x < 0)); if (ha != hb) return ha > hb; auto cr = a.cross(b); if (cr != 0) return cr > 0; return a.norm2() < b.norm2(); } } // namespace kwm_t::geometry #endif //KWM_T_GEOMETRY_POINT_HPP /** * @file convex_hull.hpp * @brief 凸包 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/geometry/convex_hull.hpp */ #ifndef KWM_T_GEOMETRY_CONVEX_HULL_HPP #define KWM_T_GEOMETRY_CONVEX_HULL_HPP #include #include /** * @brief Convex Hull (Monotone Chain) * * 点集合の凸包を求める。 * * 典型用途: * ・凸包 * ・polygon処理 * ・rotating calipers * * 計算量: * O(N log N) * * @tparam T 座標型 * * @param pts 点集合 * @param strict * true : 同一直線上の点を除く * false : 同一直線上の点を含む * * @return 凸包(反時計回り) * * verified: * https://atcoder.jp/contests/awc0103/submissions/77111025 */ namespace kwm_t::geometry { template std::vector> convex_hull(std::vector> pts, bool strict = true) { int n = pts.size(); if (n <= 1) return pts; std::sort(pts.begin(), pts.end()); std::vector> hull; hull.reserve(n * 2); auto check = [&](auto v) { return strict ? (v <= 0) : (v < 0); }; // lower hull for (const auto& p : pts) { while (hull.size() >= 2 && check((hull.back() - hull[hull.size() - 2]) .cross(p - hull.back()))) { hull.pop_back(); } hull.push_back(p); } int lower_size = hull.size(); // upper hull for (int i = n - 2; i >= 0; --i) { const auto& p = pts[i]; while ((int)hull.size() > lower_size && check((hull.back() - hull[hull.size() - 2]) .cross(p - hull.back()))) { hull.pop_back(); } hull.push_back(p); } hull.pop_back(); return hull; } /** * @brief 凸包の頂点列を、辺ベクトルが polar_cmp 順になるように巡回シフトする。 * * convex_hull() が返す凸包は反時計回りの巡回列であるため、 * 辺ベクトルも角度順には並んでいるが、始点によっては * polar_cmp の順序をまたいでしまう。 * * 例えば正方形の辺ベクトルが * * (1, 0), (0, 1), (-1, 0), (0, -1) * * の順に並んでいる場合、polar_cmp では * * (0, -1), (1, 0), (0, 1), (-1, 0) * * の順になるため、そのままでは std::merge に使えない。 * * 本関数は、辺ベクトルのうち polar_cmp で最小のものを * 先頭の辺にすることで、凸包の辺ベクトル列全体を * polar_cmp に関して昇順にする。 * * 主な用途は Minkowski Sum の計算で、複数の凸多角形の * 辺ベクトル列を std::merge するときに使用する。 * * @tparam T 点の座標型 * @param hull 反時計回りに並んだ凸包の頂点列 */ template void rotate_min_edge(std::vector>& hull) { const int n = static_cast(hull.size()); if (n <= 1) return; int pos = 0; for (int i = 1; i < n; ++i) { const Point edge = hull[(i + 1) % n] - hull[i]; const Point min_edge = hull[(pos + 1) % n] - hull[pos]; if (polar_cmp(edge, min_edge)) { pos = i; } } std::rotate(hull.begin(), hull.begin() + pos, hull.end()); } } #endif /** * @file cocircular.hpp * @brief 複数の点が同一円周上にあるかを判定 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/geometry/cocircular.hpp */ #ifndef KWM_T_GEOMETRY_COCIRCULAR_HPP #define KWM_T_GEOMETRY_COCIRCULAR_HPP #include #include //#include "point.hpp" namespace kwm_t::geometry { /** * @brief すべての点が同一円周上に存在するかを判定する。 * * 最初の3点から円を定め、残りの点がその円周上にあるかを * 整数演算で判定する。 * * 計算量: * O(N) * * @tparam T 座標型(整数型) * @param pts 点集合 * @return すべての点が同一円周上に存在するなら true * * 制約 / 注意: * - 点数が3未満の場合は true を返す。 * - 3点以上の場合、最初の3点から非一直線の3点を探す。 * - すべての点が一直線上にある場合は false を返す。 * - 重複点を許容する。 * - 内部計算に __int128_t を使用する。 * - 中間計算が __int128_t の範囲に収まること。 * - 整数座標を想定する。 * * 使用例: * std::vector> pts = { * {0, 0}, {1, 0}, {1, 1}, {0, 1} * }; * bool ok = is_cocircular(pts); // true * * verified: * 未 verified */ template bool is_cocircular(const std::vector>& pts) { using W = long long; const int n = static_cast(pts.size()); if (n < 3) return true; // 非一直線の3点を探す。 int i = 0; int j = -1; int k = -1; for (int t = 1; t < n; ++t) { if (pts[t] != pts[i]) { j = t; break; } } // すべて同じ点。 if (j == -1) return true; for (int t = 0; t < n; ++t) { if (t == i || t == j) continue; W ax = static_cast(pts[j].x) - pts[i].x; W ay = static_cast(pts[j].y) - pts[i].y; W bx = static_cast(pts[t].x) - pts[i].x; W by = static_cast(pts[t].y) - pts[i].y; if (ax * by - ay * bx != 0) { k = t; break; } } // すべての点が一直線上にある。 if (k == -1) return false; // 円周上の点 p は // x^2 + y^2 + D*x + E*y + F = 0 // を満たす。3点から D, E, F を求める。 const W x1 = pts[i].x; const W y1 = pts[i].y; const W x2 = pts[j].x; const W y2 = pts[j].y; const W x3 = pts[k].x; const W y3 = pts[k].y; const W a1 = x2 - x1; const W b1 = y2 - y1; const W c1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1; const W a2 = x3 - x1; const W b2 = y3 - y1; const W c2 = x3 * x3 + y3 * y3 - x1 * x1 - y1 * y1; const W det = a1 * b2 - a2 * b1; // D = (b1*c2 - b2*c1) / det // E = (a2*c1 - a1*c2) / det // 分母を払って整数演算だけで比較する。 const W d = b1 * c2 - b2 * c1; const W e = a2 * c1 - a1 * c2; const W f = -det * (x1 * x1 + y1 * y1) - d * x1 - e * y1; for (const auto& p : pts) { const W x = p.x; const W y = p.y; if (det * (x * x + y * y) + d * x + e * y + f != 0) { return false; } } return true; } } // namespace kwm_t::geometry #endif // KWM_T_GEOMETRY_COCIRCULAR_HPP int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vector> v(4); rep(i, 4)cin >> v[i].x >> v[i].y; std::cout << (kwm_t::geometry::is_cocircular(v) ? "YES" : "NO") << endl; return 0; }