#943299 (C++23) No.2602 Real Collider

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	Aeren
提出日時	2024-01-12 21:50:22
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	41 ms / 2,000 ms
コード長	7,026 bytes
コンパイル時間	3,367 ms
コンパイル使用メモリ	246,980 KB
実行使用メモリ	6,548 KB
最終ジャッジ日時	2024-01-12 21:50:44
合計ジャッジ時間	8,839 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	4 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	2 ms 6,548 KB
testcase_07	AC	2 ms 6,548 KB
testcase_08	AC	3 ms 6,548 KB
testcase_09	AC	2 ms 6,548 KB
testcase_10	AC	41 ms 6,548 KB
testcase_11	AC	17 ms 6,548 KB
testcase_12	AC	20 ms 6,548 KB
testcase_13	AC	10 ms 6,548 KB
testcase_14	AC	22 ms 6,548 KB
testcase_15	AC	13 ms 6,548 KB
testcase_16	AC	20 ms 6,548 KB
testcase_17	AC	22 ms 6,548 KB
testcase_18	AC	14 ms 6,548 KB
testcase_19	AC	17 ms 6,548 KB
testcase_20	AC	26 ms 6,548 KB
testcase_21	AC	14 ms 6,548 KB
testcase_22	AC	17 ms 6,548 KB
testcase_23	AC	12 ms 6,548 KB
testcase_24	AC	16 ms 6,548 KB
testcase_25	AC	17 ms 6,548 KB
testcase_26	AC	13 ms 6,548 KB
testcase_27	AC	19 ms 6,548 KB
testcase_28	AC	21 ms 6,548 KB
testcase_29	AC	18 ms 6,548 KB
testcase_30	AC	18 ms 6,548 KB
testcase_31	AC	20 ms 6,548 KB
testcase_32	AC	18 ms 6,548 KB
testcase_33	AC	20 ms 6,548 KB
testcase_34	AC	19 ms 6,548 KB
testcase_35	AC	13 ms 6,548 KB
testcase_36	AC	13 ms 6,548 KB
testcase_37	AC	21 ms 6,548 KB
testcase_38	AC	22 ms 6,548 KB
testcase_39	AC	21 ms 6,548 KB
testcase_40	AC	11 ms 6,548 KB
testcase_41	AC	24 ms 6,548 KB
testcase_42	AC	19 ms 6,548 KB
testcase_43	AC	20 ms 6,548 KB
testcase_44	AC	24 ms 6,548 KB
testcase_45	AC	16 ms 6,548 KB
testcase_46	AC	16 ms 6,548 KB
testcase_47	AC	22 ms 6,548 KB
testcase_48	AC	17 ms 6,548 KB
testcase_49	AC	14 ms 6,548 KB
testcase_50	AC	12 ms 6,548 KB
testcase_51	AC	12 ms 6,548 KB
testcase_52	AC	9 ms 6,548 KB
testcase_53	AC	20 ms 6,548 KB
testcase_54	AC	16 ms 6,548 KB
testcase_55	AC	19 ms 6,548 KB
testcase_56	AC	17 ms 6,548 KB
testcase_57	AC	16 ms 6,548 KB
testcase_58	AC	7 ms 6,548 KB
testcase_59	AC	19 ms 6,548 KB
testcase_60	AC	18 ms 6,548 KB
testcase_61	AC	14 ms 6,548 KB
testcase_62	AC	20 ms 6,548 KB
testcase_63	AC	22 ms 6,548 KB
testcase_64	AC	26 ms 6,548 KB
testcase_65	AC	14 ms 6,548 KB
testcase_66	AC	21 ms 6,548 KB
testcase_67	AC	10 ms 6,548 KB
testcase_68	AC	14 ms 6,548 KB
testcase_69	AC	9 ms 6,548 KB
testcase_70	AC	11 ms 6,548 KB
testcase_71	AC	13 ms 6,548 KB
testcase_72	AC	19 ms 6,548 KB
testcase_73	AC	16 ms 6,548 KB
testcase_74	AC	19 ms 6,548 KB
testcase_75	AC	22 ms 6,548 KB
testcase_76	AC	18 ms 6,548 KB
testcase_77	AC	19 ms 6,548 KB
testcase_78	AC	24 ms 6,548 KB
testcase_79	AC	20 ms 6,548 KB
testcase_80	AC	25 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class T>
struct point{
	T x{}, y{};
	point(){ }
	template<class U> point(const point<U> &otr): x(otr.x), y(otr.y){ }
	template<class U, class V> point(U x, V y): x(x), y(y){ }
	template<class U> point(const array<U, 2> &p): x(p[0]), y(p[1]){ }
	friend istream &operator>>(istream &in, point &p){
		return in >> p.x >> p.y;
	}
	friend ostream &operator<<(ostream &out, const point &p){
		return out << "{" << p.x << ", " << p.y << "}";
	}
	template<class U> operator array<U, 2>() const{
		return {x, y};
	}
	T operator*(const point &otr) const{
		return x * otr.x + y * otr.y;
	}
	T operator^(const point &otr) const{
		return x * otr.y - y * otr.x;
	}
	point operator+(const point &otr) const{
		return {x + otr.x, y + otr.y};
	}
	point &operator+=(const point &otr){
		return *this = *this + otr;
	}
	point operator-(const point &otr) const{
		return {x - otr.x, y - otr.y};
	}
	point &operator-=(const point &otr){
		return *this = *this - otr;
	}
	point operator-() const{
		return {-x, -y};
	}
#define scalarop_l(op) friend point operator op(const T &c, const point &p){ return {c op p.x, c op p.y}; }
	scalarop_l(+) scalarop_l(-) scalarop_l(*) scalarop_l(/)
#define scalarop_r(op) point operator op(const T &c) const{ return {x op c, y op c}; }
	scalarop_r(+) scalarop_r(-) scalarop_r(*) scalarop_r(/)
#define scalarapply(applyop, op) point &operator applyop(const T &c){ return *this = *this op c; }
	scalarapply(+=, +) scalarapply(-=, -) scalarapply(*=, *) scalarapply(/=, /)
#define compareop(op) bool operator op(const point &otr) const{ return pair<T, T>(x, y) op pair<T, T>(otr.x, otr.y); }
	compareop(>) compareop(<) compareop(>=) compareop(<=) compareop(==) compareop(!=)
#undef scalarop_l
#undef scalarop_r
#undef scalarapply
#undef compareop
	double norm() const{
		return sqrt(x * x + y * y);
	}
	long double norm_l() const{
		return sqrtl(x * x + y * y);
	}
	T squared_norm() const{
		return x * x + y * y;
	}
	// [0, 2 * pi]
	double angle() const{
		auto a = atan2(y, x);
		if(a < 0) a += 2 * acos(-1);
		return a;
	}
	// [0, 2 * pi]
	long double angle_l() const{
		auto a = atan2(y, x);
		if(a < 0) a += 2 * acosl(-1);
		return a;
	}
	point<double> unit() const{
		return point<double>(x, y) / norm();
	}
	point<long double> unit_l() const{
		return point<long double>(x, y) / norm_l();
	}
	point perp() const{
		return {-y, x};
	}
	point<double> normal() const{
		return perp().unit();
	}
	point<long double> normal_l() const{
		return perp().unit_l();
	}
	point<double> rotate(double theta) const{
		return {x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)};
	}
	point<long double> rotate_l(double theta) const{
		return {x * cosl(theta) - y * sinl(theta), x * sinl(theta) + y * cosl(theta)};
	}
	point reflect_x() const{
		return {x, -y};
	}
	point reflect_y() const{
		return {-x, y};
	}
	point reflect(const point &o = {}) const{
		return {2 * o.x - x, 2 * o.y - y};
	}
	bool parallel_to(const point &q) const{
		if constexpr(is_floating_point_v<T>) return abs(*this ^ q) <= 1e-9;
		else return abs(*this ^ q) == 0;
	}
};
template<class T, class U>
point<double> lerp(const point<T> &p, const point<U> &q, double t){
	return point<double>(p) * (1 - t) + point<double>(q) * t;
}
template<class T, class U>
point<long double> lerp_l(const point<T> &p, const point<U> &q, long double t){
	return point<long double>(p) * (1 - t) + point<long double>(q) * t;
}
template<class T>
double distance(const point<T> &p, const point<T> &q){
	return (p - q).norm();
}
template<class T>
long double distance_l(const point<T> &p, const point<T> &q){
	return (p - q).norm_l();
}
template<class T>
T squared_distance(const point<T> &p, const point<T> &q){
	return (p - q).squared_norm();
}
template<class T>
T doubled_signed_area(const point<T> &p, const point<T> &q, const point<T> &r){
	return q - p ^ r - p;
}
template<class T>
T doubled_signed_area(const vector<point<T>> &a){
	if(a.empty()) return 0;
	T res = a.back() ^ a.front();
	for(auto i = 1; i < (int)a.size(); ++ i) res += a[i - 1] ^ a[i];
	return res;
}
// [-pi, pi]
template<class T>
double angle(const point<T> &p, const point<T> &q){
	return atan2(p ^ q, p * q);
}
// [-pi, pi]
template<class T>
long double angle_l(const point<T> &p, const point<T> &q){
	return atan2l(p ^ q, p * q);
}
// Check if p->q->r is sorted by angle with respect to the origin
template<class T>
bool is_sorted_by_angle(const point<T> &origin, const point<T> &p, const point<T> &q, const point<T> &r){
	T x = p - origin ^ q - origin;
	T y = q - origin ^ r - origin;
	if(x >= 0 && y >= 0) return true;
	if(x < 0 && y < 0) return false;
	return (p - origin ^ r - origin) < 0;
}
// Check if a is sorted by angle with respect to the origin
template<class T>
bool is_sorted_by_angle(const point<T> &origin, const vector<point<T>> &a){
	for(auto i = 0; i < (int)a.size() - 2; ++ i) if(!is_sorted_by_angle(origin, a[i], a[i + 1], a[i + 2])) return false;
	return true;
}
template<class T>
bool counterclockwise(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) > 0;
}
template<class T>
bool clockwise(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) < 0;
}
template<class T>
bool colinear(const point<T> &p, const point<T> &q, const point<T> &r){
	return doubled_signed_area(p, q, r) == 0;
}
template<class T>
bool colinear(const vector<point<T>> &a){
	int i = 1;
	while(i < (int)a.size() && a[0] == a[i]) ++ i;
	if(i == (int)a.size()) return true;
	for(auto j = i + 1; j < (int)a.size(); ++ j) if(!colinear(a[0], a[i], a[j])) return false;
	return true;
}
point<double> polar(double x, double theta){
	assert(x >= 0);
	return {x * cos(theta), x * sin(theta)};
}
point<long double> polar_l(long double x, long double theta){
	assert(x >= 0);
	return {x * cosl(theta), x * sinl(theta)};
}

using pointint = point<int>;
using pointll = point<long long>;
using pointlll = point<__int128_t>;
using pointd = point<double>;
using pointld = point<long double>;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int qn;
	cin >> qn;
	pointll a, b, c;
	cin >> a >> b >> c;
	a *= 2, b *= 2, c *= 2;
	auto circular = [&](pointll p, pointll a, pointll b, pointll c){
		a -= p, b -= p, c -= p;
		return (a.squared_norm() * (b ^ c) + b.squared_norm() * (c ^ a) + c.squared_norm() * (a ^ b)) * (doubled_signed_area(a, b, c) > 0 ? 1 : -1) >= 0;
	};
	for(auto qi = 0; qi < qn; ++ qi){
		pointll p;
		cin >> p;
		p *= 2;
		for(auto rep = 3; rep; -- rep){
			if(squared_distance(a, b) >= squared_distance(b, c) + squared_distance(c, a)){
				auto center = (a + b) / 2;
				squared_distance(center, a) >= squared_distance(center, p) ? cout << "Yes\n" : cout << "No\n";
				goto NEXT;
			}
			swap(a, b);
			swap(b, c);
		}
		circular(p, a, b, c) ? cout << "Yes\n" : cout << "No\n";
		NEXT:;
	}
	return 0;
}

/*

*/

yukicoder

結果

テストケース

ソースコード