Level 2. 교점에 별 만들기

Level 2. 교점에 별 만들기

 

 

전에 봤을 때 별을 직접 그려야 하는 문제인 줄 알고 넘겼었는데, 막상 자세히 읽어보니 그렇게 어려운 문제는 아니었다.

• 가장 바깥 쪽의 점들만 표시하는 건 줄 알고 기겁했었는데, 그냥 모든 정수 점들을 구하면 되는 문제여서 쉬웠다.

 

교점을 구하는 것은 주어진 공식을 사용하면 되고, 그 중 좌표가 정수인 교점만 활용하면 된다.

• 교점은 두 직선을 통해 구하므로, 이중 for문을 사용하면 된다.
• int끼리 곱하면서 범위가 넘어갈 수 있기 때문에 long 타입에 저장해준다.
• 교점을 구하면서 정답 영역의 최소와 최대 지점을 함께 갱신한다.

 

그리고 마지막에 정답에 점들을 찍어주면 된다.

• Y 좌표는 maxY - y가 되고, X 좌표는 x - minX가 됨에 주의해야 한다.

 

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

using namespace std;

struct Point
{
    long x;
    long y;
};

bool intersection_point(vector<int>& line1, vector<int>& line2, Point& result)
{
    long ad_bc = long(line1[0]) * line2[1] - long(line1[1]) * line2[0];

    if (ad_bc == 0)
        return false;

    long bf_ed = long(line1[1]) * line2[2] - long(line1[2]) * line2[1];
    long ec_af = long(line1[2]) * line2[0] - long(line1[0]) * line2[2];

    if ((bf_ed % ad_bc) || (ec_af % ad_bc))
        return false;

    result.x = bf_ed / ad_bc;
    result.y = ec_af / ad_bc;

    return true;
}

vector<string> solution(vector<vector<int>> line)
{
    vector<string> answer;
    size_t n = line.size();

    long minX = LONG_MAX, minY = LONG_MAX, maxX = LONG_MIN, maxY = LONG_MIN;
    vector<Point> intsctPoints;

    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            Point result;

            if (intersection_point(line[i], line[j], result))
            {
                minX = min(minX, result.x);
                minY = min(minY, result.y);

                maxX = max(maxX, result.x);
                maxY = max(maxY, result.y);

                intsctPoints.emplace_back(result);
            }
        }
    }

    answer = vector<string>(maxY - minY + 1, string(maxX - minX + 1, '.'));

    for (Point& p : intsctPoints)
        answer[maxY - p.y][p.x - minX] = '*';

    return answer;
}