#943728 (C++17) No.2602 Real Collider

• 問題: No.2602 Real Collider
• ユーザー: cho435
• 提出日時: 2024-01-12 23:16:37
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 936 ms / 2,000 ms
• コード長: 1,812 bytes
• コンパイル時間: 8,750 ms
• コンパイル使用メモリ: 520,064 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-09-28 00:00:04
• 合計ジャッジ時間: 32,300 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,944 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	3 ms; 6,944 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	936 ms; 6,940 KB
testcase_11	AC	284 ms; 6,944 KB
testcase_12	AC	299 ms; 6,940 KB
testcase_13	AC	144 ms; 6,940 KB
testcase_14	AC	319 ms; 6,940 KB
testcase_15	AC	207 ms; 6,940 KB
testcase_16	AC	325 ms; 6,940 KB
testcase_17	AC	355 ms; 6,940 KB
testcase_18	AC	207 ms; 6,944 KB
testcase_19	AC	248 ms; 6,944 KB
testcase_20	AC	404 ms; 6,944 KB
testcase_21	AC	193 ms; 6,940 KB
testcase_22	AC	237 ms; 6,944 KB
testcase_23	AC	158 ms; 6,940 KB
testcase_24	AC	235 ms; 6,944 KB
testcase_25	AC	247 ms; 6,944 KB
testcase_26	AC	187 ms; 6,940 KB
testcase_27	AC	270 ms; 6,940 KB
testcase_28	AC	319 ms; 6,940 KB
testcase_29	AC	245 ms; 6,940 KB
testcase_30	AC	269 ms; 6,940 KB
testcase_31	AC	339 ms; 6,944 KB
testcase_32	AC	286 ms; 6,944 KB
testcase_33	AC	344 ms; 6,940 KB
testcase_34	AC	325 ms; 6,944 KB
testcase_35	AC	201 ms; 6,940 KB
testcase_36	AC	183 ms; 6,940 KB
testcase_37	AC	356 ms; 6,948 KB
testcase_38	AC	353 ms; 6,940 KB
testcase_39	AC	357 ms; 6,940 KB
testcase_40	AC	164 ms; 6,940 KB
testcase_41	AC	383 ms; 6,944 KB
testcase_42	AC	299 ms; 6,940 KB
testcase_43	AC	296 ms; 6,944 KB
testcase_44	AC	418 ms; 6,940 KB
testcase_45	AC	251 ms; 6,940 KB
testcase_46	AC	246 ms; 6,940 KB
testcase_47	AC	368 ms; 6,944 KB
testcase_48	AC	266 ms; 6,940 KB
testcase_49	AC	237 ms; 6,944 KB
testcase_50	AC	189 ms; 6,940 KB
testcase_51	AC	201 ms; 6,944 KB
testcase_52	AC	130 ms; 6,940 KB
testcase_53	AC	328 ms; 6,944 KB
testcase_54	AC	248 ms; 6,940 KB
testcase_55	AC	271 ms; 6,944 KB
testcase_56	AC	277 ms; 6,944 KB
testcase_57	AC	253 ms; 6,940 KB
testcase_58	AC	96 ms; 6,944 KB
testcase_59	AC	324 ms; 6,944 KB
testcase_60	AC	264 ms; 6,940 KB
testcase_61	AC	208 ms; 6,944 KB
testcase_62	AC	338 ms; 6,940 KB
testcase_63	AC	377 ms; 6,940 KB
testcase_64	AC	453 ms; 6,940 KB
testcase_65	AC	210 ms; 6,940 KB
testcase_66	AC	355 ms; 6,940 KB
testcase_67	AC	159 ms; 6,940 KB
testcase_68	AC	190 ms; 6,944 KB
testcase_69	AC	127 ms; 6,940 KB
testcase_70	AC	158 ms; 6,940 KB
testcase_71	AC	208 ms; 6,940 KB
testcase_72	AC	316 ms; 6,940 KB
testcase_73	AC	256 ms; 6,944 KB
testcase_74	AC	331 ms; 6,944 KB
testcase_75	AC	344 ms; 6,940 KB
testcase_76	AC	306 ms; 6,940 KB
testcase_77	AC	314 ms; 6,944 KB
testcase_78	AC	427 ms; 6,944 KB
testcase_79	AC	327 ms; 6,944 KB
testcase_80	AC	400 ms; 6,940 KB

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using mint = atcoder::modint998244353;
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;
using ld = boost::rational<Bint>;

int main(){
	int q;
	cin>>q;
	vector<pair<int,int>> vp(3);
	vector<pair<int,int>> vq(q);
	for(auto&[x,y]:vp) cin>>x>>y;
	for(auto&[x,y]:vq) cin>>x>>y;
	ld cx,cy,r2=-1;
	rep(i,3){
		int x1,x2,y1,y2;
		x1=vp.at(1).first-vp.at(0).first;
		x2=vp.at(2).first-vp.at(0).first;
		y1=vp.at(1).second-vp.at(0).second;
		y2=vp.at(2).second-vp.at(0).second;
		if(x1*x2+y1*y2<=0){
			cx=(vp.at(1).first+vp.at(2).first);
			cy=(vp.at(1).second+vp.at(2).second);
			cx/=2;
			cy/=2;
			r2=(vp.at(1).first-vp.at(2).first)*(vp.at(1).first-vp.at(2).first)
					+(vp.at(1).second-vp.at(2).second)*(vp.at(1).second-vp.at(2).second);
			r2/=4;
			break;
		}
		swap(vp.at(0),vp.at(1));
		swap(vp.at(1),vp.at(2));
	}
	if(r2<0){
		ld k=0;
		k+=(vp.at(0).first-vp.at(2).first)*(vp.at(1).first-vp.at(2).first);
		k+=(vp.at(0).second-vp.at(2).second)*(vp.at(1).second-vp.at(2).second);
		ld dv=0;
		dv+=(vp.at(0).first-vp.at(2).first)*(vp.at(1).second-vp.at(2).second);
		dv-=(vp.at(0).second-vp.at(2).second)*(vp.at(1).first-vp.at(2).first);
		assert(abs(dv)>0);
		k/=dv;
		cx=(vp.at(0).first+vp.at(1).first)+k*(vp.at(0).second-vp.at(1).second);
		cx/=2;
		cy=(vp.at(0).second+vp.at(1).second)-k*(vp.at(0).first-vp.at(1).first);
		cy/=2;
		r2=(vp.at(0).first-cx)*(vp.at(0).first-cx)+(vp.at(0).second-cy)*(vp.at(0).second-cy);
	}
	for(auto[x,y]:vq){
		ld d2=(x-cx)*(x-cx)+(y-cy)*(y-cy);
		if(d2<=r2) cout<<"Yes\n";
		else cout<<"No\n";
	}
}