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

평면 xy에 수많은 점들이 주어진다. 이때, 두 점을 이어서 직선을 만들 것인데, 이전에 그렸던 직선과 평행한 직선은 다시 그을 수 없다.

문제를 해결하기위해 먼저 각각의 좌표를 오름차순으로 정렬했다.

그리고 각각의 점들간의 모든 기울기를 계산하여 set에 저장했다.

알고 있듯이 set은 중복되는 값은 알아서 저장하지 않기 때문에, 중복되는 기울기는 제외하고 점들간에 계산된 기울기는 set에 모두 저장된다.

그러므로 set의 크기가 곧 상원이가 그린 직선의 최댓값이 된다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main(void)
{
    int T = 1;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        vector< pair<int, int> > v;
        set<double> s;
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            v.push_back(make_pair(x, y));
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                s.insert(((double)(v[j].second - v[i].second) / (double)(v[j].first - v[i].first)));
            }
        }
        printf("#%d %d\n", test_case, s.size());
    }
    return 0;
}