結果

問題 No.168 ものさし
ユーザー やまぞうやまぞう
提出日時 2015-03-30 01:44:51
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,762 bytes
コンパイル時間 466 ms
コンパイル使用メモリ 65,744 KB
最終ジャッジ日時 2024-04-27 02:07:07
合計ジャッジ時間 861 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘ll result()’:
main.cpp:95:40: error: ‘sqrt’ was not declared in this scope
   95 |                                 d = ll(sqrt(double(d2)));
      |                                        ^~~~

ソースコード

diff # 

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

typedef int64_t ll;

struct Node
{
	ll x, y;

	Node()
	{}

	Node(ll x, ll y)
		: x(x), y(y)
	{}

};

ll norm2(const Node& pt1, const Node& pt2)
{
	ll dx = pt1.x - pt2.x;
	ll dy = pt1.y - pt2.y;
	return dx * dx + dy * dy;
}

vector<Node> nodes;

struct Edge
{
	size_t n1, n2;
	ll dist2;

	Edge()
	{}

	Edge(size_t n1, size_t n2, ll d2)
		: n1(n1), n2(n2), dist2(d2)
	{}

	struct less
	{
		bool operator()(const Edge& e1, const Edge& e2) const
		{
			return e1.dist2 < e2.dist2;
		}
	};
};


void input(istream& in)
{
	size_t n;
	in >> n;
	nodes.resize(n);
	for (size_t i = 0; i < n; i++) in >> nodes[i].x >> nodes[i].y;
}

ll result()
{
	vector<Edge> edges;
	edges.reserve(nodes.size() * (nodes.size() - 1) / 2);
	for (size_t i1 = 0; i1 < nodes.size() - 1; i1++) {
		for (size_t i2 = i1 + 1; i2 < nodes.size(); i2++) {
			edges.push_back(Edge(i1, i2, norm2(nodes[i1], nodes[i2])));
		}
	}
	sort(edges.begin(), edges.end(), Edge::less());

	vector<int> root(nodes.size());
	for (size_t i = 0; i < root.size(); i++) {
		root[i] = i;
	}

	ll d = 0;
	for (size_t i = 0; i < edges.size(); i++) {
		Edge& edge = edges[i];
		int n1 = edge.n1;
		while (root[n1] != n1) n1 = root[n1];
		int n2 = edge.n2;
		while (root[n2] != n2) n2 = root[n2];
		if (n1 != n2) {
			root[max(n1, n2)] = min(n1, n2);

			int n3 = root.back();
			while (root[n3] != n3) n3 = root[n3];
			if (n3 == 0) {
				ll d2 = edge.dist2;
				d = ll(sqrt(double(d2)));
				d = (d + 9) / 10 * 10;
				while (d * d < d2) {
					d += 10;
				}
				break;
			}
		}
	}
	return d;
}

int main(int argc, char **argv)
{
	input(cin);
	cout << result() << endl;
}
0