結果

問題 No.168 ものさし
ユーザー やまぞう
提出日時 2015-03-30 01:44:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,762 bytes
コンパイル時間 743 ms
コンパイル使用メモリ 65,476 KB
最終ジャッジ日時 2024-11-14 19:01:14
合計ジャッジ時間 1,132 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0