직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.
제한사항
line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
line의 가로(열) 길이는 3입니다.
line의 각 원소는 [A, B, C] 형태입니다.
A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
A = 0이면서 B = 0인 경우는 주어지지 않습니다.
정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
별이 한 개 이상 그려지는 입력만 주어집니다.
풀이
입출력 예시
풀이
먼저 교점이 존재하는지, 존재하면 어디인지를 확인할 방법은 문제의 마지막에 주어져있다.
AD - BC = 0인 경우 두 직선은 평행 또는 일치한다.
이를 이용해 AD - BC 가 0이 아니면서 교점이 정수일 때에만 그 위치에 '*'을 찍어준다. answer에 표현할 때에는 x는 작은 값, y는 큰 값부터 적용되어야 한다.
주의할 사항은 A, B, C가 -100,000 이상 100,000 이하의 수가 들어온다는 점이다. 즉, 모든 곱셈의 결과가 int 형의 최댓값(또는 최솟값)을 넘기는 경우가 발생할 수 있다는 점이다. 그러므로, long long 형을 사용해 오버플로우(또는 언더플로우)에 대비해야 한다. (27번과 28번이 아마 이 부분에 관한 테스트 케이스 였던 것 같다.)
#include <string>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;
vector<string> solution(vector<vector<int>> line) {
vector<string> answer;
set<pair<long long, long long>> pos;
for (int i = 0; i < line.size() - 1; i++) {
for (int j = i + 1; j < line.size(); j++) {
long long AD_BC = (long long)line[i][0] * line[j][1] - (long long)line[i][1] * line[j][0];
if (AD_BC != 0) {
double x = ((double)line[i][1] * line[j][2] - (double)line[i][2] * line[j][1]) / AD_BC;
double y = ((double)line[i][2] * line[j][0] - (double)line[i][0] * line[j][2]) / AD_BC;
if (x - (long long)x == 0 && y - (long long)y == 0) {
pos.insert({ x, y });
}
}
}
}
long long min_x = 9223372036854775807;
long long max_x = -9223372036854775808;
long long min_y = 9223372036854775807;
long long max_y = -9223372036854775808;
for (const auto& p : pos) {
min_x = min(p.first, min_x);
min_y = min(p.second, min_y);
max_x = max(p.first, max_x);
max_y = max(p.second, max_y);
}
for (long long y = min_y; y <= max_y; y++) {
string tmp = "";
for (long long x = min_x; x <= max_x; x++) {
tmp += ".";
}
answer.push_back(tmp);
}
for (const auto& p : pos) {
answer[abs(p.second - max_y)][abs(p.first - min_x)] = '*';
}
return answer;
}
