5170. 상원이의 직선 긋기 게임

5170. 상원이의 직선 긋기 게임

D5 치고는 굉장히 쉬운 문제였다.

일단 주어진 점의 갯수가 200개 이므로, 나올 수 있는 직선의 갯수는 200C2 로 19900 개가 된다.

따라서 모든 경우의 수를 탐색한다고 하더라도 시간 초과가 나올 수 없는 문제라서 완전탐색을 이용해서 문제를 풀었다.

2중 for문을 통해서 전체의 직선을 모두 구하고, get_incline 함수를 이용해서 직선의 기울기를 중복 생각없이 모두 vector 에 담았다.

그리고 sort 를 이용해서 vector 를 정렬하고, 중복되는 수를 빼가면서 수를 세줬다.

이때 tmp 값을 초기에 10000으로 설정한 이유는, x,y 좌표의 범위가 -1000 에서 1000 사이 이므로 기울기가 가장 클 때는 1000 이다.

따라서 1000보다 큰 값을 tmp 로 두었다. 그리고 기울기가 무한대가 되는 부분은 9999 를 return 하도록 함수를 짰다.

이 문제에서 조심할 점은 소숫점이 나오므로 익숙한 int 형이 아닌 모두 double 형으로 실수값을 이용해야 한다는 점이다. 

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
typedef struct {
    double x;
    double y;
}Pos;
using namespace std;
 
double get_incline(Pos p1, Pos p2)
{
    if (p1.x - p2.x == 0)
        return 9999;
 
    return ((p1.y - p2.y) / (p1.x - p2.x));
}
 
int main()
{
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        int n;
        Pos p[200];
        double tmp = 10000;
        int ans = 0;
        vector<double> value;
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            cin >> p[i].x >> p[i].y;
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                double v=get_incline(p[i], p[j]);
                value.push_back(v);
            }
        }
 
        sort(value.begin(), value.end());
        for (int i = 0; i < value.size(); i++) {
            if (value[i] != tmp) {
                tmp = value[i];
                ans++;
            }
        }
 
        cout << "#" << t << " " << ans << endl;
 
    }
 
    return 0;
}