結果

問題 No.168 ものさし
ユーザー maimai
提出日時 2017-08-22 22:45:07
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,635 bytes
コンパイル時間 966 ms
コンパイル使用メモリ 110,464 KB
実行使用メモリ 47,232 KB
最終ジャッジ日時 2024-10-15 04:27:22
合計ジャッジ時間 13,161 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 320 ms
29,440 KB
testcase_01 AC 32 ms
19,840 KB
testcase_02 AC 30 ms
20,096 KB
testcase_03 AC 33 ms
20,608 KB
testcase_04 AC 33 ms
20,480 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 32 ms
20,352 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 46 ms
24,344 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SandboxCSharp
{
    class Solver
    {

        void Solve()
        {
            int n = io.ScanInt();

            List<Tuple<int, int>> points = new List<Tuple<int, int>>();

            for (int i = 0; i < n; ++i)
            {
                int x, y;
                x = io.ScanInt();
                y = io.ScanInt();
                points.Add(new Tuple<int, int>(x, y));
            }

            List<Tuple<double, int, int>> edges = new List<Tuple<double, int, int>>();

            for (int i = 0; i < n; ++i)
            {
                int x1 = points[i].Item1;
                int y1 = points[i].Item2;
                for (int j = i + 1; j < n; ++j)
                {
                    int x2 = points[j].Item1;
                    int y2 = points[j].Item2;

                    edges.Add(new Tuple<double, int, int>(Hypot(x1 - x2, y1 - y2), i, j));
                    
                }
            }

            edges.Sort();

            UnionFind unionfind = new UnionFind(n);

            double length = 0;
            foreach (var edge in edges)
            {
                int i = edge.Item2;
                int j = edge.Item3;
                if (unionfind.Union(i, j))
                {
                    length = edge.Item1;
                }
            }

            io.WriteLine($"{Math.Ceiling(length/10)*10}");
        }

        private double Hypot(double x, double y)
        {
            double u = Math.Max(Math.Abs(x), Math.Abs(y));
            double v = Math.Min(Math.Abs(x), Math.Abs(y));
            return u * Math.Sqrt(1.0 + (v / u) * (v / u));
        }

        // =================================================
        // =================================================

        Stdio io;
        bool isjdg;
        static void Main()
        {
            var s = new Solver();
            s.Solve();
            s.io.Flush();
        }
        Solver(Stdio _io = null)
        {
            isjdg = _io == null;
            io = _io == null ? new Stdio() : io;
        }

        void Exit()
        {
            if (isjdg)
            {
                io.Flush();
                Environment.Exit(0);
            }
            else
                throw new HaltException();
        }
    }
    class Stdio
    {
        protected string[] stack = new string[0];
        protected int stackptr = 0;
        protected StringBuilder outbuff = new StringBuilder();

        public virtual int ScanInt()
        {
            return Check() ? int.Parse(stack[stackptr++]) : 0;
        }
        public virtual long ScanLong()
        {
            return Check() ? long.Parse(stack[stackptr++]) : 0;
        }
        public virtual string ScanString()
        {
            return Check() ? stack[stackptr++] : string.Empty;
        }
        public virtual double ScanDouble()
        {
            return Check() ? double.Parse(stack[stackptr++]) : 0;
        }
        protected virtual bool Check()
        {
            if (stackptr < stack.Length) return true;
            var l = Console.ReadLine();
            if (l == null) return false;
            stack = l.Split(' ').ToArray(); stackptr = 0;
            return Check();
        }
        public Stdio Write(long v) { return Write($"{v}"); }
        public Stdio WriteLine(long v) { return WriteLine($"{v}"); }
        public Stdio Write(string str)
        {
            outbuff.Append(str);
            return this;
        }
        public Stdio WriteLine(string str = "")
        {
            outbuff.AppendLine(str);
            return this;
        }
        public virtual Stdio Flush()
        {
            Console.Write(outbuff.ToString());
            outbuff.Clear();
            return this;
        }
    }
    class HaltException : Exception { }

    class UnionFind
    {
        private int[] data;

        public UnionFind(int size)
        {
            data = Enumerable.Repeat(-1, size).ToArray();
        }

        public bool Union(int x, int y)
        {
            x = Root(x); y = Root(y);
            if (x != y)
            {
                if (data[y] < data[x])
                    { var t = y;y = x;x = t; } // swap
                data[x] += data[y]; data[y] = x;
            }
            return x != y;
        }

        public bool Find(int x, int y) { return Root(x) == Root(y); }
        public int Root(int x) { return data[x] < 0 ? x : data[x] = Root(data[x]); }
        public int Size(int x) { return -data[Root(x)]; }
    }
}
0