結果

問題 No.168 ものさし
コンテスト
ユーザー kuuso1
提出日時 2015-03-21 01:43:47
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 706 ms / 2,000 ms
コード長 5,497 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,537 ms
コンパイル使用メモリ 110,848 KB
実行使用メモリ 49,020 KB
最終ジャッジ日時 2024-12-24 07:05:36
合計ジャッジ時間 6,811 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 #
raw source code 

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;
		PriorityQueue<Pair2> PQ=new PriorityQueue<Pair2>();
		for(int i=1;i<N;i++){
			PQ.Push(new Pair2(i,Dist[0,i]));
		}
		
		while(PQ.Count>0){
			var p=PQ.Top;PQ.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]){
					PQ.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 PriorityQueue<T> where T:IComparable<T>{

	//T:IComparable
	//IComparerかComparisonを指定してインスタンス化する事も可
	//引数なしインスタンス化⇒ComparedToで比較
	//大きいものほどTopへ

	enum typeCompare{
		isIComparerable=1,
		useIComparer=2,
		useDComparison=3
	}

	List<T> buffer;
	typeCompare tComp;
	IComparer<T> Cmper;
	Comparison<T> Cmp;
	
	public PriorityQueue(IComparer<T> comparer_){
		this.buffer=new List<T>();
		tComp=typeCompare.useIComparer;
		Cmper=comparer_;
		Cmp=null;
	}
	public PriorityQueue(){
		this.buffer=new List<T>();
		tComp=typeCompare.isIComparerable;
	}
	public PriorityQueue(Comparison<T> cmp_){
		this.buffer=new List<T>();
		tComp=typeCompare.useDComparison;
		Cmp=cmp_;
		Cmper=null;
	}
	public PriorityQueue(int capacity,IComparer<T> comparer_){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.useIComparer;
		Cmper=comparer_;
	}
	public PriorityQueue(int capacity){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.isIComparerable;
	}
	public PriorityQueue(int capacity,Comparison<T> cmp_){
		this.buffer=new List<T>(capacity);
		tComp=typeCompare.useDComparison;
		Cmp=cmp_;
	}
	

	void PushHeap(List<T> arr,T elem){
		int n=arr.Count;
		buffer.Add(elem);
		
		if(tComp==typeCompare.isIComparerable){
			try{
			while(n!=0){
				int i=(n-1)/2;
				if(arr[n].CompareTo(arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
			}
		        catch (Exception e){
				Console.WriteLine("{0} Exception caught.", e);
		        }
		}else if(tComp==typeCompare.useIComparer){
			try{
			while(n!=0){
				int i=(n-1)/2;
				if(Cmper.Compare(arr[n],arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
			}
		        catch (Exception e){
				Console.WriteLine("{0} Exception caught.", e);
		        }
		}else if(tComp==typeCompare.useDComparison){
			while(n!=0){
				int i=(n-1)/2;
				if(Cmp(arr[n],arr[i]) > 0){
					T tmp=arr[n];arr[n]=arr[i];arr[i]=tmp;
				}
				n=i;
			}
		}
	}
	
	void PopHeap(List<T> arr){
		int n=arr.Count - 1;
		arr[0] = arr[n];
		arr.RemoveAt(n);
		
		if(tComp==typeCompare.isIComparerable){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(arr[j].CompareTo(arr[j+1])<0))j++;
				if (arr[i].CompareTo(arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
      		}else if(tComp==typeCompare.useIComparer){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(Cmper.Compare(arr[j],arr[j+1])<0))j++;
				if (Cmper.Compare(arr[i],arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
		}else if(tComp==typeCompare.useDComparison){
			for (int i=0,j;(j = 2*i +1)<n;){
				if((j!=n - 1)&&(Cmp(arr[i],arr[j])<0))j++;
				if (Cmp(arr[i],arr[j])<0){
					T tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
				}
				i=j;
			}
		}
	}
	
	
	
	public void Push(T elem){
		PushHeap(this.buffer, elem);
	}
	
	public void Pop(){
		PopHeap(this.buffer);
	}
	
	public bool Contains(T elem){
		return this.buffer.Contains(elem);
	}
	public T Top{
		get{return this.buffer[0];}
	}
	
	public int Count{
		get{return this.buffer.Count;}
	}
	
	public T this[int i]{
		get{return this.buffer[i];}
	}
	
	public bool IsEmpty{
		get{return this.buffer.Count==0;}
	}
}
0