BOJ 2013 선그리기

www.acmicpc.net/problem/2013

2013번: 선그리기

 

먼저 생각난 것은 두 점으로 일차함수를 만들어 저장하는 것이였다. 

근데 입력이 소수여서 정밀도 처리가 필요했다. 나는 문자로 입력을 받아 정수부, 소수부를 반환시켜주는 함수를 만들었다.

void scan(int& a, int& b){
  char s[8];
  scanf("%s",s);
  a = 0, b = 0;
  int index=0;
  for(;s[index] && s[index] != '.'; index++){
    a *= 10;
    a += s[index] - '0';
  }
  if(!s[index]) return;

  ++index;
  for(int i=0; i<2; i++){
    b *= 10;
    if(s[index+i]) b += s[index+i] - '0';
  }
}

 

두 점으로 y = (b/a)x + (c/d) (a > 0, c >=0) 꼴의 일차함수를 만들어 저장했다.

y= n, x = m 꼴의 함수도 처리 가능하게 했다. 

이때, 같은 일차함수를 만들 수 있는 점들의 쌍이 여러개일 수 있으므로, key 값이 { {a,b}, {c,d} }, value 가 priority queue인 자료구조를 만들어 사용하기로 했다.

map<pair<pair<int, int>, pair<int, int>>, priority_queue<pair<int, int>>> m;

 

map을 사용한 이유는, 같은 일차함수를 찾기 위해 O(n) 만큼 탐색하는 것을 막기 위해서이며, value로 priority queue는 추후 한꺼번에 그을 수 있는 점들의 쌍들을 찾기 위해 사용했다. (vector로 입력받고, 정렬하여 사용해도 된다)

 

모든 입력을 처리한 뒤, 한꺼번에 그을 수 있는 점들의 쌍들을 찾았다.

크게 어려운건 아니고, 점들의 쌍 중 작은 x의 값을 기준으로 정렬하여, 현재 그을 수 있는 x좌표의 min, max를 변경해가면서 계산한다.

만약, min, max 안에 현재 x값이 들어간다면, 기존에 그은 선들과 현재 쌍이 겹친다는 의미이므로, 한꺼번에 그릴 수 있다.

만약 x값이 min, max 밖에 있다면, 기존에 그은 선들과 함께 그릴 수 없다. 현재 쌍의 x 좌표들로 min, max를 갱신하여 겹처 그릴 수 있는 점들을 추가해간다.

 

이 방법은 x에 대해 정렬되어있기 때문에 가능하다.

제출 코드는 다음과 같다.

#include <cstdio>
#include <set>
#include <map>
#include <cmath>
#include <queue>

using namespace std;

int gcd(int a, int b){
    if(b==0) return a;
    else  return gcd(b, a%b);
}

void scan(int& a, int& b){
  char s[8];
  scanf("%s",s);
  a = 0, b = 0;
  int index=0;
  for(;s[index] && s[index] != '.'; index++){
    a *= 10;
    a += s[index] - '0';
  }
  if(!s[index]) return;

  ++index;
  for(int i=0; i<2; i++){
    b *= 10;
    if(s[index+i]) b += s[index+i] - '0';
  }
}

int main(){
    
    
    int n; scanf("%d",&n);
    int answer = 0;

    map<pair<pair<int, int>, pair<int, int>>, priority_queue<pair<int, int>>> m;
    
    for(int i=0;i<n;i++){
        
        int x11, x12, y11, y12, x21, x22, y21, y22;
        scan(x11, x12);
        scan(y11, y12);
        scan(x21, x22);
        scan(y21, y22);
        
        int b = (y21*100 + y22) - (y11*100 + y12);
        int a = (x21*100 + x22) - (x11*100 + x12);

        if(a == 0){
            b = 1;
        }
        else if(b == 0){
            a = 1;
        }
        else{
            int g = gcd( abs(b), abs(a));
            a /= g, b /= g;
            if(a < 0){
                a = -a, b = -b;
            }
        }
        //x = 1 같은 그래프 처리 기울기 무한대

        int c = (-b*(x21*100 + x22) + a*(y21*100 + y22));
        int d = 100*a;

        if(c == 0){
            d = 1;
        }
        else if(d == 0){
            c = (x21*100 + x22);
        }
        else{
            int g2 = gcd(abs(c),abs(d));
            c /= g2, d /= g2;
            if(c < 0){
                c = -c, d = -d;
            }
        }
        pair<pair<int, int>, pair<int, int>> k = {{a,b}, {c,d}};
        if(m.find({{a,b}, {c,d}}) == m.end()){
            m[k] = priority_queue<pair<int, int>>();
        }
        int x1 = x11*100+x12;
        int x2 = x21*100+x22;
        if (x1 == x2){
          x1 = y11*100 + y12;
          x2 = y21*100 + y22;
        }
        
        if(x1 > x2 )
            m[k].push({x1, x2});
        else
            m[k].push({x2, x1});
    }
    
    int idx = 0;
    for(auto it = m.begin(); it!= m.end(); ++it){

        auto before = it->second.top();
        int min = before.second;
        int max = before.first;
        answer += it->second.size();
        it->second.pop();
        while(it->second.size()){
          auto after = it->second.top();
          if(max >= after.first && after.first >= min){
            answer -= 1;
            if(min > after.second)
              min = after.second;
          }
          else{
            max = after.first;
            min = after.second;
          }
          before = after;
          it->second.pop();
        }
    }

    printf("%d\n", answer);

    return 0;
}

 

소수 처리때문에 애를 먹었던 문제였다. 처음엔 scanf format으로 "%d.%d" 로 숫자를 입력받았는데, 1.01, 1.1인 경우의 차이를 구분할 수 없었다. 또한, 소수부 없이 입력하는 경우도 고려하지 못했다.

열심히 풀었지만, 비효율적인 코드인 것 같다. 리팩토링이 필요하다.

다른 사람들 코드를 보니 좀더 깔끔하게 구현했었다. 정밀도에 대해서 이해도가 있다면, 이 문제를 더 깔끔하게 풀 수 있었을 것이다.