#784132 (C++14) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: rinrion
• 提出日時: 2022-08-03 17:26:21
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 3 ms / 1,000 ms
• コード長: 1,235 bytes
• コンパイル時間: 2,314 ms
• 実行使用メモリ: 3,820 KB
• スコア: 4,521,707
• 最終ジャッジ日時: 2022-08-03 17:26:25
• 合計ジャッジ時間: 3,857 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 3,740 KB
testcase_01	AC	2 ms; 3,820 KB
testcase_02	AC	2 ms; 3,764 KB
testcase_03	AC	2 ms; 3,640 KB
testcase_04	AC	2 ms; 3,752 KB
testcase_05	AC	2 ms; 3,708 KB
testcase_06	AC	2 ms; 3,656 KB
testcase_07	AC	2 ms; 3,664 KB
testcase_08	AC	2 ms; 3,740 KB
testcase_09	AC	2 ms; 3,696 KB
testcase_10	AC	2 ms; 3,712 KB
testcase_11	AC	2 ms; 3,736 KB
testcase_12	AC	3 ms; 3,688 KB
testcase_13	AC	2 ms; 3,652 KB
testcase_14	AC	2 ms; 3,768 KB
testcase_15	AC	2 ms; 3,592 KB
testcase_16	AC	2 ms; 3,592 KB
testcase_17	AC	2 ms; 3,692 KB
testcase_18	AC	2 ms; 3,664 KB
testcase_19	AC	2 ms; 3,692 KB
testcase_20	AC	2 ms; 3,752 KB
testcase_21	AC	2 ms; 3,716 KB
testcase_22	AC	3 ms; 3,756 KB
testcase_23	AC	2 ms; 3,692 KB
testcase_24	AC	2 ms; 3,740 KB
testcase_25	AC	2 ms; 3,740 KB
testcase_26	AC	3 ms; 3,772 KB
testcase_27	AC	2 ms; 3,740 KB
testcase_28	AC	3 ms; 3,712 KB
testcase_29	AC	3 ms; 3,640 KB

ソースコード

#include <bits/stdc++.h>
#include<chrono> //時間計測
using namespace std;

double eu2(double x1,double y1, double x2, double y2){
	double s= sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	return s*s;
}


int main(){
	int n,m;
	cin>>n>>m;
	
	vector<int>a(n),b(n);
	for(int i=0; i<n; i++){
		cin>>a[i]>>b[i];
	}

	vector<vector<tuple<double,int>>>dis_i(100,vector<tuple<double,int>>());
	
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(i!=j){
				dis_i[i].push_back(make_tuple(eu2(a[i],b[i],a[j],b[j]),j));
			}
		}
		sort(dis_i[i].begin(),dis_i[i].end());
	}


	vector<pair<int,int>>tr;
	bitset<100>visited;
	int now=0;
	visited[now]=true;
	tr.emplace_back(1,1);

	while(true){
		bool jdg=false;
		for(int i=0; i<100; i++){
			if(!visited[get<1>(dis_i[now][i])]){
				int next=get<1>(dis_i[now][i]);
				tr.emplace_back(1,next+1);
				now=next;
				visited[next]=true;
				jdg=true;
				break;
			}
		}
		if(!jdg)break;
	}

	tr.emplace_back(1,1);

	vector<pair<int,int>>cd(8);//ロボてりーの位置　×8
		for(int i=0; i<8; i++){
		get<0>(cd[i])=0;
		get<1>(cd[i])=0;
	}
	
		for(auto x:cd){
		cout<<get<0>(x)<<" "<<get<1>(x)<<endl;
	}
	cout<<tr.size()<<endl;
	for(auto x:tr){
		cout<<get<0>(x)<<" "<<get<1>(x)<<endl;
	}

}