結果

問題 No.168 ものさし
ユーザー kuuso1
提出日時 2015-03-20 00:49:43
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 595 ms / 2,000 ms
コード長 3,116 bytes
コンパイル時間 1,101 ms
コンパイル使用メモリ 109,952 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-12-24 07:00:21
合計ジャッジ時間 5,945 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.Collections.Generic;
 
class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}
class Sol{
    public void Solve(){
        
        long[,] Dist=new long[N,N];
        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                long l=0;
                long r=(long)2e9;
                long c=(l+r)/2;
                while(r-l>1){
                    c=(l+r)/2;
                    if(c*c>d2(P[i],P[j])){
                        r=c;
                    }else{
                        l=c;
                    }
                }
                while(c*c>d2(P[i],P[j]))c--;
                while(c*c<d2(P[i],P[j]))c++;
                if(c%10!=0)c+=10-c%10;
                Dist[i,j]=Dist[j,i]=c;
            }
        }
        
        long Max=0;
        bool[] used=new bool[N];
        used[0]=true;
        SkewHeap<Pair2> SH=new SkewHeap<Pair2>();
        for(int i=1;i<N;i++){
            SH.Push(new Pair2(i,Dist[0,i]));
        }
        
        while(SH.Count>0){
            var p=SH.Top;SH.Pop();
            if(used[p.Pos])continue;
            
            Max=Math.Max(Max,p.Cost);
            used[p.Pos]=true;
            if(p.Pos==N-1)break;
            for(int i=0;i<N;i++){
                if(!used[i]){
                    SH.Push(new Pair2(i,Dist[p.Pos,i]));
                }
            }
        }
        Console.WriteLine(Max);
        
        
        
        
        
    }
    int N;
    Pair[] P;
    public Sol(){
        N=ri();
        P=new Pair[N];
        for(int i=0;i<N;i++){
            var d=rla();
            P[i]=new Pair(d[0],d[1]);
        }
    }
    class Pair{
        public long X,Y;
        public Pair(long x,long y){
            X=x;Y=y;
        }
    }
    long d2(Pair p,Pair q){
        return (p.X-q.X)*(p.X-q.X)+(p.Y-q.Y)*(p.Y-q.Y);
    }
    
    
    
    static String rs(){return Console.ReadLine();}
    static int ri(){return int.Parse(Console.ReadLine());}
    static long rl(){return long.Parse(Console.ReadLine());}
    static double rd(){return double.Parse(Console.ReadLine());}
    static String[] rsa(){return Console.ReadLine().Split(' ');}
    static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
    static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
    static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}
class Pair2 : IComparable<Pair2> {
    public int Pos;
    public long Cost;
    public Pair2(int p, long c) {
        Pos = p; Cost = c;
    }
    public int CompareTo(Pair2 t) {
        //return this.Cost > t.Cost ? -1 : this.Cost < t.Cost ? 1 : 0;
        return this.Cost > t.Cost ? 1 : this.Cost < t.Cost ? -1 : 0;
    }
}
class SkewHeap<T> where T:IComparable<T>{
    public int Count{
        get{return cnt;}
        private set{cnt=value;}
    }
    
    public SkewHeap(){
        root=null;
        this.Count=0;
    }
    
    public void Push(T v){
        NodeSH<T> p=new NodeSH<T>(v);
        root=NodeSH<T>.Meld(root,p);
        this.Count++;
    }
    
    public void Pop(){
        if(root==null)return;
        root=NodeSH<T>.Meld(root.L,root.R);
        this.Count--;
    }
    
    public T Top{
        get{return root.Val;}
    }
    
    int cnt;
    NodeSH<T> root;
    
    class NodeSH<S> where S : IComparable<S> {
        public NodeSH<S> L, R;
        public S Val;
        public NodeSH(S v){
            Val = v;
            L = null; R = null;
        }
        public static NodeSH<S> Meld(NodeSH<S> a, NodeSH<S> b){
            if(a == null)return b;
            if (b == null) return a;
            if (a.Val.CompareTo(b.Val) > 0) swap(ref a, ref b);
            a.R = Meld(a.R, b);
            swap(ref a.L, ref a.R);
            return a;
        }
        static void swap<U>(ref U x, ref U y) {
            U t = x; x = y; y = t;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1