[Programmers]10週目-頂点に星を作成

問題の説明

n本の直線(Ax+By+C=0と表すことができる)が与えられた場合、その直線の頂点の整数座標に星が描画されます.
例えば、5本の直線

2x - y + 4 = 0

-2x - y + 4 = 0

-y + 1 = 0

5x - 8y - 12 = 0

5x + 8y + 12 = 0

座標平面の上に描画する場合は、下図のようにします.

このとき、すべての頂点の座標は(4、1)、(4、-4)、(-4、-4)、(-4、1)、(0,1.5)、(2.1、-0.19)、(-2.1、-0.19)、(-1.5、-0.19)、(-1.5、-1.5、1.0)である.ここで、整数のみで表される座標は、(4,1)、(4,-4)、(-4,-4)、(-4,1)、(0,4)である.
整数で表される頂点に星を描くと、次のようになります.

上の図が文字列として表示されている場合、星図の描画部分*は空です(グリッドの交差).次のように表示されます.

グリッドは無限幅で、すべての星を含む最小サイズを表示するだけです.
だから正解は.

.
直線A,B,Cに関する情報を含むパラメトリック配列行.このとき、求解関数を完了し、すべての星を含む最小矩形を返します.

せいげんじょうけん

線の縦(行)長は2または1000の自然数より小さい.

行の横(列)の長さは3です.

lineの各要素は[A,B,C]形式である.

A,B,Cは−1000以上100000以下の整数である.

に無数の頂点の直線対を生成しない.

A=0の場合、B=0は指定されません.

正解は1000*1000サイズ以内に表示されます.

星を表示する入力は1つ以上しか提供されません.

ソースコード

import java.util.*;

class Node {
    long x;
    long y;
 
    public Node(long x, long y) {
        this.x = x;
        this.y = y;
    }
}

class Solution {
    ArrayList<Node> list = new ArrayList<Node>();
    public static long mx = Long.MIN_VALUE, nx = Long.MAX_VALUE;
    public static long my = Long.MIN_VALUE, ny = Long.MAX_VALUE;
    
    // 교점에 해당되는지 Check
    boolean chkDot(long x, long y){
        for(int i=0;i<list.size();i++){
            if(list.get(i).x == x && list.get(i).y == y) {
                return true;
            }
        }
        return false;
    }
    
    public String[] solution(int[][] line) {
        // 교점 좌표 구하기
        for(int i=0;i<line.length-1;i++) {
            for(int j=i+1;j<line.length;j++) {
            	long A = line[i][0], B = line[i][1], E = line[i][2];
                long C = line[j][0], D = line[j][1], F = line[j][2];
                if(A*D-B*C == 0) 
                    break;
                double x = (double) (B*F-E*D) / (A*D-B*C);
                double y = (double) (E*C-A*F) / (A*D-B*C);
                // 교점 좌표가 정수인지 Check
                if(x == (long) x && y == (long) y) {
                    // x,y 최소/최대값 구하기 
                    mx = Math.max(mx, (long)x);
                    my = Math.max(my, (long)y);
                    nx = Math.min(nx, (long)x);
                    ny = Math.min(ny, (long)y);
                    list.add(new Node((long)x,(long)y));
                }
            }
        }
        
        String[] answer = new String[(int)(my-ny+1)];
        int idx = 0; // answer index
        for(long i=my;i>=ny;i--) { // y는 최대->최소
            String s = "";
            for(long j=nx;j<=mx;j++) { // x는 최소->최대
                // 교점에 해당하면 "*"
                if(chkDot(j,i)) {
                    s += "*";
                    continue;
                }
                // 해당하지 않으면 "."
                s += ".";
            }
            answer[idx] = s;
            idx++;
        }
        return answer;
    }
}

に答える

最初に頂点に対応する場合は、リストをソートして*を表示し、順番に比較しようとしますが、エラーが発生しました.これは簡単にドアを回って検査すればいい問題です.😥
上記の問題を解決した結果、ケース29のエラーが発生しました.
結局、他の人の質問の内容を調べて、オーバーフローを防ぐためにA~Fをlong型と宣言せざるを得なかった.
やっと解けたのだから、もっと頑張らなければならない.😫 🧐