#1194922 (C++23) No.3005 トレミーの問題

提出ソース
結果

問題	No.3005 トレミーの問題
コンテスト
ユーザー	kwm_t
提出日時	2026-10-24 14:04:46
言語	C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) コンパイル: `g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	1 ms / 2,000 ms
	+ 899µs
コード長	9,856 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,009 ms
コンパイル使用メモリ	380,660 KB
実行使用メモリ	9,920 KB
最終ジャッジ日時	2026-10-26 23:10:34
合計ジャッジ時間	6,663 ms
ジャッジサーバーID （参考情報）	judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 35
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#include <atcoder/all>
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<int,int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> 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 <cstdint>
#include <cmath>

 /**
  * @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<class T>
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<class T>
Point<double> rotate(const Point<T>& 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<class T>
bool polar_cmp(const Point<T>& a, const Point<T>& 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 <vector>
#include <algorithm>

 /**
  * @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<class T>
std::vector<Point<T>> convex_hull(std::vector<Point<T>> pts, bool strict = true) {

	int n = pts.size();
	if (n <= 1) return pts;

	std::sort(pts.begin(), pts.end());

	std::vector<Point<T>> 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 <class T>
void rotate_min_edge(std::vector<Point<T>>& hull) {
	const int n = static_cast<int>(hull.size());
	if (n <= 1) return;

	int pos = 0;
	for (int i = 1; i < n; ++i) {
		const Point<T> edge = hull[(i + 1) % n] - hull[i];
		const Point<T> 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 <vector>
#include <cstdint>

 //#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<Point<long long>> pts = {
 *       {0, 0}, {1, 0}, {1, 1}, {0, 1}
 *   };
 *   bool ok = is_cocircular(pts); // true
 *
 * verified:
 *   未 verified
 */
template <class T>
bool is_cocircular(const std::vector<Point<T>>& pts) {
	using W = long long;

	const int n = static_cast<int>(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<W>(pts[j].x) - pts[i].x;
		W ay = static_cast<W>(pts[j].y) - pts[i].y;
		W bx = static_cast<W>(pts[t].x) - pts[i].x;
		W by = static_cast<W>(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<kwm_t::geometry::Point<long long>> 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;
}
yukicoder

結果

ソースコード
