結果

問題 No.168 ものさし
ユーザー mai
提出日時 2017-08-22 22:26:36
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,626 bytes
コンパイル時間 933 ms
コンパイル使用メモリ 119,720 KB
実行使用メモリ 827,116 KB
最終ジャッジ日時 2024-10-15 04:27:05
合計ジャッジ時間 3,744 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 3
other AC * 2 WA * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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])
                    x ^= y ^= x ^= y; // 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