1858번: 기울기가 가장 큰 두 점
평면상에 N개의 서로 다른 점들이 주어져 있을 때, 그 중 임의의 두 점을 지나는 직선의 기울기의 절댓값이 가장 큰 두 점을 찾고 싶다. 두 점의 좌표가 (x1, y1), (x2, y2) 라고 할 때, 기울기의 절댓
www.acmicpc.net
완전탐색으로 알고리즘을 짜면 시간초과가 걸리니 적당히 샘플링 할 방법을 찾아야합니다.
여기서 어느 점들을 골라 비교하면 될까를 생각하게 되는데, 결론적으로는 x 축을 기준으로 인접한 점들을 비교해주면 됩니다.
어떤 좌표군을 탐색하겠습니다.
우리는 해당 좌표군을 2진 탐색의 방식으로 가장 기울기의 절댓값이 큰 선분이 어떤 식으로 존재하는지 탐색하겠습니다.
x 축을 기준으로 시작과 끝에 있는 점을 잇고(1) 가운데에 있는 점을 시작과 끝에 있는 점과 이으면(2)(3)
(1) 의 기울기보다 (2) 와 (3) 중 하나의 기울기가 클 수 밖에 없습니다.
위 논리를 기반으로 시작과 가운데, 가운데와 끝을 순차적으로 탐색하면,
결국 현재 탐색된 기울기의 절댓값의 최댓값은 해당 선분을 잇는 양 끝점을 시작과 끝으로 하는 탐색에서 어떠한 두 선분 중 하나보다 기울기의 절댓값이 작을 것임을 알 수 있습니다.
결국 이 탐색은 인접한 두 점이 남을 때 까지 행해지며 결국 인접한 두 점을 잇는 선분 중 기울기의 절댓값이 최대가 나오는 선분이 나온다는 사실을 알 수 있습니다.
그렇다면 단순히 인접한 두 점을 탐색하면 되냐면 예외가 있습니다.
만약 같은 기울기가 연속적으로 나온다면 가장 작은 A와 B 를 출력해야 한다는 조건을 만족하지 않을 수 있기 때문입니다. 때문에 기울기가 같고 연속적으로 나온 상황은 따로 처리해줘야 합니다.
또, 기울기의 절댓값이 같은 경우는 A 와 B 를 비교해 출력하도록 처리해줘야 합니다.
결과적으로 탐색하는 순차적으로 인접하는 점들을 탐색하되 예외만 처리해주면 되겠습니다.
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <set>
using namespace std;
// 정렬 함수
bool sort_idx(array<int, 3>& arr_1, array<int, 3>& arr_2) {
// x 오름차순
return arr_1[0] < arr_2[0];
}
int main(void) {
// 입력
int N;
cin >> N;
// 좌표 정보 벡터, { { 좌표, 번호 }, 활성화 }
vector<array<int, 3>> idxs;
for (int i = 0; i < N; i++) {
array<int, 3> temp_arr;
cin >> temp_arr[0] >> temp_arr[1];
temp_arr[2] = i + 1;
idxs.push_back(temp_arr);
}
// x 오름차순, y 오름차순으로 정렬
sort(idxs.begin(), idxs.end(), sort_idx);
// 최대 기울기, 해당 번호
float max_incline = 0;
int max_A, max_B, max_i;
// x 좌표가 인접한 좌표끼리 기울기 계산
for (int i = 0; i < N - 1; i++) {
float incline = static_cast<float>(idxs[i + 1][1] - idxs[i][1]) / static_cast<float>(idxs[i + 1][0] - idxs[i][0]);
// 기울기의 절댓값이 최대 기울기의 절댓값보다 크면
if (abs(incline) > abs(max_incline)) {
// 기울기 최댓값 최신화
max_incline = incline;
// 번호, 인덱스 최신화
max_A = min(idxs[i + 1][2], idxs[i][2]);
max_B = max(idxs[i + 1][2], idxs[i][2]);
max_i = i + 1;
}
// 기울기의 절댓값이 최대 기울기의 절댓값과 같으면
if (abs(incline) == abs(max_incline)){
// 값이 같고 연속되는 인덱스이면
if (incline == max_incline and max_i == i) {
// max_A, max_B 후보, 중복 제거
set<int> candid_set = { max_A, max_B, idxs[i][2], idxs[i + 1][2] };
// 벡터로 치환
vector<int> candid_vec(candid_set.begin(), candid_set.end());
// 정렬
sort(candid_vec.begin(), candid_vec.end());
// 가장 작은 두 값 할당
max_A = candid_vec[0];
max_B = candid_vec[1];
}
// 절댓값이 같거나 값이 같은데 연속되지 않는 경우
else {
// x 축 기준으로 앞에 있는 점이 max_A 보다 번호가 작거나
// x 축 기준으로 뒤에 있는 점이 max_A 보다 번호가 작거나
// x 축 기준으로 앞에 있는 점이 max_A 와 같고 뒤에 있는 점이 max_B 보다 작거나
// x 축 기준으로 뒤에 있는 점이 max_A 와 같고 앞에 있는 점이 max_B 보다 작으면
if (idxs[i][2] < max_A or
idxs[i + 1][2] < max_A or
(idxs[i][2] == max_A and idxs[i + 1][2] < max_B) or
(idxs[i + 1][2] == max_A and idxs[i][2] < max_B)) {
// 작은 값은 max_A
max_A = min(idxs[i + 1][2], idxs[i][2]);
; // 큰 값은 max_B
max_B = max(idxs[i + 1][2], idxs[i][2]);
}
}
}
}
cout << max_A << " " << max_B;
}
