[アルゴリズム]Algospot FORTRESS

17300 ワード
algorithm algospot テキストリンク
ソース:https://algospot.com/judge/problem/read/FORTRESS

質問する



中世の城や要塞はもっと広い領域を守るために城壁が多かったそうです.世界で最も偏屈な領主が建てたストラゴ要塞が示している.この要塞は図のように、巨大な円形の外壁の中に、複数の円形の城壁が重なり、どの城壁にもドアがなく、城壁を通るには梯子を登って城壁を下りなければならない.最近、ある場所から別の場所に移動するのに時間がかかるという不満が出ており、英珠は要塞内にトンネルを建設し、往来が不便な場所を結ぶことにした.計画を立てるために、要塞内で互いに行き来するために最も城壁を越える必要がある場所を2つ見つけたい.たとえば、上図では、星が示す2つの場所の間を移動するには、城壁を5回越えなければなりません.
城壁の情報を得ると、計算プログラムを作成して、2つの最も城壁を越える必要がある場所の間を移動するために何回越える必要があるかを計算することができます.

入力


入力された最初の行は、テストケースの数C(1<=C<=100)を示します.各試験例の第1行において、城壁の数はN(1<=N<=100)であった.次に、N行は、各城壁の位置と大きさに関する情報xi、yi、riを含む3つの整数である.(0<=xi,yi<=1000,1<=ri<=1000,0<=i

しゅつりょく


各テストキャビネットは、最大数回城壁を越えて1行2点の間を移動するように印刷されます.

正しいコード

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int t, n, longest;
int x[101], y[101], r[101];
struct Tree {
	vector<Tree*> children;
};

int sqr(int x)
{
	return x * x;
}

int sqrdist(int a, int b)
{
	return (sqr(y[a] - y[b]) + sqr(x[a] - x[b]));
}

bool enclose(int a, int b)
{
	return r[a] > r[b] && sqrdist(a, b) < sqr(r[a] - r[b]);
}

bool isChild(int parent, int child)
{
	if (!enclose(parent, child))
		return false;
        
	for (int i = 0; i < n; i++)
    	{
		if (i != parent && i != child && enclose(parent, i) && enclose(i, child))
			return false;
	}
	return true;
}

Tree* getTree(int root)
{
	Tree* tmp = new Tree();
	for (int i = 0; i < n; i++)
    	{
		if (isChild(root, i))
        	{
			tmp->children.push_back(getTree(i));
		}
	}
	return tmp;
}

int height(Tree* root)
{
	vector<int> heights;
	for (int i = 0; i < root->children.size(); i++)
		heights.push_back(height(root->children[i]));

	if (heights.empty()) return 0;

	sort(heights.begin(), heights.end());

	if (heights.size() >= 2)
		longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);

	return heights.back() + 1;
}

int solve(Tree* root)
{
	longest = 0;
	int h = height(root);
	return max(longest, h);
}
int main()
{
	cin >> t;
	while (t--)
    {
		cin >> n;

		for (int i = 0; i < n; i++) 
			cin >> x[i] >> y[i] >> r[i];

		Tree* T = getTree(0);

		cout << solve(T) << endl;
	}
	return 0;
}

解答と思考過程


ツリー構造でデータを入れる過程で、馴染みがないので難しいです.
本を読みながら、コードを書きながら、木の書き方を学びました.
それも焼き続ける
ベースサブネットの更新
JAVAの元のexcelファイルをエクスポートして、速くて通用して便利でwordドキュメントをエクスポートすることができます