結果

問題 No.168 ものさし
ユーザー fjafjafjafjafjafja
提出日時 2017-09-21 00:12:51
言語 Java21
(openjdk 21)
結果
MLE  
実行時間 -
コード長 1,588 bytes
コンパイル時間 3,277 ms
コンパイル使用メモリ 74,756 KB
実行使用メモリ 836,904 KB
最終ジャッジ日時 2023-08-08 03:30:08
合計ジャッジ時間 8,112 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

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