취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29131번 문제인 Хобби이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/29131 

어떤 가상의 직선이 평면을 쓸고 가는 경우를 상상해보자. 단, 이 직선은 같은 점을 두 번 이상 쓸지 않고, 주어진 점을 한번에 둘 이상 지나는 경우도 없다고 가정하자.

이 때 이 가상의 직선이 평면에서 만난 점을 차례대로 둘씩 이으면 총 n/2개의 서로 교차하지 않는 선분의 쌍을 얻을 수 있다. 어떤 두 선분이 교차한다면 직선이 쓸고 가는 과정에서 어떤 한 선분을 이루는 두 점을 지나는 사이에 다른 선분의 끝점을 적어도 하나 지나가야만 하기 때문이다.

이제 이와 같은 직선을 하나 잡아 문제를 해결하자. 글쓴이는 기울기가 음의 무한대에 가까운 직선을 x축방향으로 쓰는 식으로 생각해 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
pair<pair<int, int>, int> points[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		points[i] = make_pair(make_pair(x, y), i + 1);
	}

	sort(points, points + N);

	cout << N / 2 << '\n';
	for (int i = 0; i + 1 < N; i += 2) {
		cout << points[i].second << ' ' << points[i + 1].second << '\n';
	}
}