#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
• 実行時間: 955 ms / 2,000 ms
• コード長: 1,812 bytes
• コンパイル時間: 10,065 ms
• コンパイル使用メモリ: 551,760 KB
• 実行使用メモリ: 6,676 KB
• 最終ジャッジ日時: 2024-01-12 23:17:15
• 合計ジャッジ時間: 36,474 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,548 KB
testcase_01	AC	3 ms; 6,548 KB
testcase_02	AC	4 ms; 6,548 KB
testcase_03	AC	3 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	2 ms; 6,548 KB
testcase_09	AC	2 ms; 6,548 KB
testcase_10	AC	955 ms; 6,548 KB
testcase_11	AC	297 ms; 6,548 KB
testcase_12	AC	322 ms; 6,548 KB
testcase_13	AC	150 ms; 6,676 KB
testcase_14	AC	344 ms; 6,676 KB
testcase_15	AC	243 ms; 6,676 KB
testcase_16	AC	348 ms; 6,676 KB
testcase_17	AC	384 ms; 6,676 KB
testcase_18	AC	226 ms; 6,676 KB
testcase_19	AC	270 ms; 6,676 KB
testcase_20	AC	430 ms; 6,676 KB
testcase_21	AC	204 ms; 6,676 KB
testcase_22	AC	263 ms; 6,676 KB
testcase_23	AC	169 ms; 6,676 KB
testcase_24	AC	243 ms; 6,676 KB
testcase_25	AC	256 ms; 6,676 KB
testcase_26	AC	206 ms; 6,676 KB
testcase_27	AC	295 ms; 6,676 KB
testcase_28	AC	345 ms; 6,676 KB
testcase_29	AC	258 ms; 6,676 KB
testcase_30	AC	277 ms; 6,676 KB
testcase_31	AC	380 ms; 6,676 KB
testcase_32	AC	304 ms; 6,676 KB
testcase_33	AC	361 ms; 6,676 KB
testcase_34	AC	350 ms; 6,676 KB
testcase_35	AC	223 ms; 6,676 KB
testcase_36	AC	197 ms; 6,676 KB
testcase_37	AC	382 ms; 6,676 KB
testcase_38	AC	393 ms; 6,676 KB
testcase_39	AC	388 ms; 6,676 KB
testcase_40	AC	180 ms; 6,676 KB
testcase_41	AC	433 ms; 6,676 KB
testcase_42	AC	343 ms; 6,676 KB
testcase_43	AC	333 ms; 6,676 KB
testcase_44	AC	455 ms; 6,676 KB
testcase_45	AC	262 ms; 6,676 KB
testcase_46	AC	267 ms; 6,676 KB
testcase_47	AC	404 ms; 6,676 KB
testcase_48	AC	294 ms; 6,676 KB
testcase_49	AC	258 ms; 6,676 KB
testcase_50	AC	189 ms; 6,676 KB
testcase_51	AC	212 ms; 6,676 KB
testcase_52	AC	147 ms; 6,676 KB
testcase_53	AC	421 ms; 6,676 KB
testcase_54	AC	272 ms; 6,676 KB
testcase_55	AC	304 ms; 6,676 KB
testcase_56	AC	308 ms; 6,676 KB
testcase_57	AC	292 ms; 6,676 KB
testcase_58	AC	104 ms; 6,676 KB
testcase_59	AC	349 ms; 6,676 KB
testcase_60	AC	281 ms; 6,676 KB
testcase_61	AC	231 ms; 6,676 KB
testcase_62	AC	356 ms; 6,676 KB
testcase_63	AC	391 ms; 6,676 KB
testcase_64	AC	508 ms; 6,676 KB
testcase_65	AC	227 ms; 6,676 KB
testcase_66	AC	380 ms; 6,676 KB
testcase_67	AC	170 ms; 6,676 KB
testcase_68	AC	209 ms; 6,676 KB
testcase_69	AC	138 ms; 6,676 KB
testcase_70	AC	167 ms; 6,676 KB
testcase_71	AC	228 ms; 6,676 KB
testcase_72	AC	342 ms; 6,676 KB
testcase_73	AC	287 ms; 6,676 KB
testcase_74	AC	358 ms; 6,676 KB
testcase_75	AC	384 ms; 6,676 KB
testcase_76	AC	328 ms; 6,676 KB
testcase_77	AC	368 ms; 6,676 KB
testcase_78	AC	441 ms; 6,676 KB
testcase_79	AC	351 ms; 6,676 KB
testcase_80	AC	440 ms; 6,676 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";
	}
}