프로그래머스 교점에 별 만들기 C++

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다. 

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."  

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다. 

따라서 정답은 

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"  

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

 

 

=> 두 직선의 교점의 공식을 알아야 합니다. 

=> ax + by + C =0 , lx + my + N =0

=> 두 직선의 교점의 공식입니다. 

• bn - cm / am - bl 
• cl - an / am -bl

=> 분모가 0일 경우, 두 직선은 평행이거나 일치합니다. 하지만 문제의 조건에서 일치하는 경우는 주어지지 않는다고 하므로 일치하는 경우는 염두에 두지 않아도 됩니다. 

=> 풀이는 아래에 그림으로 대체하겠습니다. 

 

 

#include <string>
#include <vector>
#include <climits> 
#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;
//교점 저장할 pair형 vector
vector<pair<int, int>> crossP;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    
    long long maxX = LLONG_MIN;  long long maxY = LLONG_MIN;
    long long minX = LLONG_MAX;  long long minY = LLONG_MAX;
    
   for(int i=0; i<line.size(); i++)
   {
       //직선1
       long long A = line[i][0];
       long long B = line[i][1];
       long long C = line[i][2];
       for(int j=i+1; j<line.size(); j++)
       {
           //직선2
            long long L = line[j][0];
            long long M = line[j][1];
            long long N = line[j][2];
           //분모
           long long deno = (A*M) - (B*L);
           //분자_x좌표
           long long moleX = (B*N)-(C*M);
           //분자_y좌표
           long long moleY = (C*L)-(A*N);
           
           //분모가 '0'인 경우, 교점이 없음
           if(deno == 0) continue;
           
           //교점이 정수가 아닌 경우, 건너뜀
           if(moleX % deno || moleY %deno)continue;
                      
           int X = moleX / deno;
           int Y = moleY / deno;
        
           crossP.push_back(make_pair(X,Y));
           maxX = max(maxX, (long long)X); minX = min(minX, (long long)X);
           maxY = max(maxY, (long long)Y); minY = min(minY, (long long)Y);   
       }
        long long row = maxX - minX +1; //x축
        long long col = maxY - minY +1; //y축
           
       string tmp(row, '.');
       answer.assign(col, tmp);
       
       
        for(int i=0;i<crossP.size();i++)
        {
            long long y = crossP[i].second;
            long long x =crossP[i].first;
            answer[maxY-y][x-minX]='*';
        }
       
   }

    return answer;
}