[백준/BOJ] 1619 점 고르기 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/1619

[설명]
적어도 세 점을 골라야 하며, 고른 점들 중 임의로 두 개를 선택했을 때 적어도 하나의 다른 점이 있어야 한다. 한 직선 위의 서로 다른 세 점이 있는 경우를 생각했을 때, 이 직선 위가 아닌 부분에 다른 점이 있다면 조건을 만족하지 못한다. 따라서 한 직선 위에 최대의 점의 개수를 구하고 3개보다 적게 있다면 -1을 출력하면 된다.

이를 위해 한 점을 필수로 포함하고 이와 다른 점들과의 기울기를 unordered_map에 저장하면서 그 직선 위의 점들의 개수를 세도록 solve함수를 만들어서 이를 해결하였다. 이때 x축에 수직인 경우를 주의해야 한다.

[코드]

#include<iostream>
#include<unordered_map>
#define INF 50000
using namespace std;

int n, arr[1001][2];
bool check[1001];

int solve(int ind) {
    unordered_map<float, int> um;
    int i, ans = 0;
    check[ind] = true;
    for (i = 0; i < n; i++) {
        if (check[i]) continue;
        if (arr[ind][0] == arr[i][0]) {
            if (um.count(INF)) um[INF]++;
            else um.insert({ INF,1 });
            ans = max(ans, um[INF]);
        }
        else {
            float k = (float)(arr[ind][1] - arr[i][1]) / (arr[ind][0] - arr[i][0]);
            if (um.count(k)) um[k]++;
            else um.insert({ k,1 });
            ans = max(ans, um[k]);
        }
    }
    return ans + 1;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int i, ans = 0;
    cin >> n;
    for (i = 0; i < n; i++) cin >> arr[i][0] >> arr[i][1];
    for (i = 0; i < n - 2; i++) ans = max(ans, solve(i));
    if (ans > 2) cout << ans;
    else cout << -1;
}