#205800 (Java) No.168 ものさし

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
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;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX