[프로그래머스] 교점에 별 만들기

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/87377

제한사항

• 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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

풀이

실패
범위 제약을 신경쓰지 않아서 헤매다가 문제를 틀렸다.
우선 A, B, C의 최대값이 10만인데, 판별식에서 두 수를 곱하게 되는데 10만 x 10만 = 100억 > 21억 이므로 int 형을 사용하면 오버플로우가 발생한다. 나는 10만 x 10만 의 결과값을 10억으로 착각해 int형을 사용해놓고 계속 다른 곳에서 문제점을 찾았다…ㅜ

코드

// 09:06 ~ 
#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<long long,long long>> v;
    long long a,b,e; //Ax + By + E = 0
    long long c,d,f; //Cx + Dy + F = 0
    long long x,y;
    long long min_x = 10000000001, min_y = 10000000001, max_x = -10000000001, max_y = -10000000001;
    for(int i = 0; i < line.size(); ++i){
        a = line[i][0]; b = line[i][1]; e = line[i][2];
        for(int j = i + 1; j < line.size(); ++j){
            c = line[j][0]; d = line[j][1]; f = line[j][2];
            if(a*d == b*c) continue;
            if((b*f - e*d)%(a*d - b*c)!= 0 || (e*c - a*f)%(a*d - b*c) != 0) continue;
            x = (b*f - e*d)/(a*d - b*c);
            y = (e*c - a*f)/(a*d - b*c);
            
            if(x > max_x) max_x = x;
            if(x < min_x) min_x = x;
            if(y > max_y) max_y = y;
            if(y < min_y) min_y = y;
            v.push_back({x,y});
        }
    }
    
    string temp;
    temp.append(max_x - min_x + 1, '.');
   
    for(int i = 0; i < max_y - min_y + 1; ++i){
        answer.push_back(temp);
    }
    for(int i =0; i < v.size(); ++i){
        long long nx = v[i].first;
        long long ny = v[i].second;
        answer[max_y - ny][nx - min_x] = '*';
    }
    return answer;
}