結果

問題 No.168 ものさし
コンテスト
ユーザー fjafjafja
提出日時 2017-09-21 00:12:51
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,588 bytes
コンパイル時間 3,510 ms
コンパイル使用メモリ 77,680 KB
実行使用メモリ 835,512 KB
最終ジャッジ日時 2024-11-08 09:23:15
合計ジャッジ時間 10,414 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.Scanner;

public class N168
{
	static int n;
	static Long[] x,y;
	static int[] utree;
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		x=new Long[n];
		y=new Long[n];
		utree=new int[n];
		for(int i=0;i<n;i++)
		{
			x[i]=sc.nextLong();
			y[i]=sc.nextLong();
			utree[i]=-1;
		}

		long begin=0, end=dist(x[0],y[0],x[n-1],y[n-1]);

		while(begin!=end)
		{
			long m=(begin+end)/2;m/=10;m++;m*=10;
			if(m==end){break;}
			if(isok(m))
			{
				end=m;
			}
			else
			{
				begin=m;
			}

		}
		System.out.println(end);


	}

	static boolean isok(long mono)
	{
		clear();
		makeutree(mono);
		return ufind(0,n-1);

	}

	static void clear()
	{
		for(int i=0;i<n;i++)
		{
			utree[i]=-1;
		}
	}
	static void makeutree(long mono)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				if(utree[j]==-1&&islink(i,j,mono))
				{
					utree[j]=i;
				}
			}
		}
	}

	static boolean ufind(int taget,int x)
	{
		if(utree[x]==taget)
		{
			return true;
		}
		else if(utree[x]==-1)
		{
			return false;
		}
		else
		{
			return ufind(taget,utree[x]);
		}
	}



	static boolean islink(int i,int j,long mono)//物差しで二点が届くかどうか
	{return dist(x[i],y[i],x[j],y[j])<=mono;}

	static long dist(long x,long y,long xx,long yy)//二点をつなぐのに必要な物差しの長さを出力
	{
		long beki=(x-xx)*(x-xx)+(y-yy)*(y-yy);
		long minmono=10*(int)Math.floor(Math.sqrt(beki)/10);
		while(true)
		{
			if(minmono*minmono>=beki){break;}
			minmono+=10;
		}
		return minmono;

	}

}
0