[BOJ]14658号:天上流星が飛び交う(Java)

質問する (Gold 4)

14658号:天上流星が飛び交う

に答える

NとMの範囲は50万で、全て検索するとタイムアウトします.
しかし,Kの個数は100個以下であるため,Kを用いて探索すればよい.

上の画像は問題例を座標に表示しています.
双星をゲートとして回転し,x座標y座標をそれぞれ抽出してその範囲を探索する.
赤い点は、各番号から抽出されたx、y座標を表し、これを座標セグメントとしてL*Lの範囲にナビゲートすればよい.
星がエッジに存在するほど、より多くの星を含むことができると考えられています.
上記の例では、5番点のxを抽出する、2番点のyを抽出した赤点からトランポリンを解放すると、
最も多くの星が含まれていることがわかります!

コード#コード#

package bruteForce;

import java.util.*;
import java.io.*;

public class BOJ_14658_하늘에서별똥별이빗발친다 {
    static int N, M, L, K;
    static List<int[]> stars;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        stars = new ArrayList<>();
        for(int i =0 ; i < K ; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            stars.add(new int[]{x, y});
        }
        int res = Integer.MIN_VALUE;
        for(int[] s1: stars){
            for(int[] s2: stars){
                res = Math.max(res, boundStar(s1[0], s2[1]));
            }
        }
        System.out.println(K-res);
    }

    private static int boundStar(int i, int j) {
        int res = 0;
        for(int[] s:stars){
            if(i<=s[0]&&s[0]<=i+L && j<=s[1]&&s[1]<=j+L ) res++;
        }
        return res;
    }
}

送信

50000*500000は完全に覗き込むことに失敗しました!(~ダメだと分かっていたけど、念のため~だから来た!~)