boj, 백준) 10254. 고속도로 (C / C++)

1. 문제 링크

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

10254번: 고속도로

2. 문제 개요

n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.

 

도시의 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾는 프로그램을 작성하시오.

 

3. 문제 힌트

그냥 Brute Force로 푼다면 이문제는 O(n^2) 시간 내에 풀 수 있다. 하지만 N이 20만이다. 그래서 O(nlogn)이나.. 그런 방법으로 풀어야 한다.

 

이 문제는 회전하는 캘리퍼스 (Rotate Calipers)라는 알고리즘을 사용해야 한다.

 

4. 문제 풀이

우선 컨벡스 헐 알고리즘은 알고 있다고 가정하고 풀이를 쓰겠습니다.

 

Convex Hull을 구해서 Vector에 들어가 있다고 가정하자.

 

Rotate Calipers알고리즘을 사용하기 위해서는 Convex hull을 이루는 아무 두 점을 잡아서 시작하면 된다.

보통 시작점과, 그다음점을 기준으로 한다.

 

초기화

이런 식으로 시작할 수 있겠다.

이제, 벡터 i->i_next와 j->j_next를 구해서,  ccw를 구해줄 것이다.

현재 i와 j는 반시계 방향으로 돌고 있기 때문에 저기 두 벡터가 반시계 방향이라면 j는 j_next가 되고 j_next도 다음점을 가리키게 된다.

두 벡터가 시계방향을 나타낸다면, 그때는 최장거리의 후보가 될 수 있기 때문에 거리를 측정해야 한다.

 

작성한 코드에서는 시계방향으로 탐색하도록 했다.(기존의 컨벡스 헐 알고리즘(그라함스캔)이라면 y좌표가 가장 작은 점부터 시계 반대방향으로 스택에 쌓아가지만, 스택에서 꺼낸다면 시계방향으로 순회하기 때문에 두 벡터가 시계방향이면 진행, 반시계 방향을 나타내면 거리를 측정하도록 했다.

 

첫번째 거리 측정

물론 정답은 이 거리가 되겠지만, j가 위의 그래프의 점을 나타내는 경우 두 벡터는 시계방향이 되고, (외적이 음수) 

거리를 측정하여 max_dist값에 저장해둔다.

 

그리고 다음 상태는 i가 한 칸 움직인

 

2번째 상태

이 상태가 된다.

 

이런 방식으로, i가 한 바퀴 돌 때까지 진행하면 된다.

알고리즘면에서 코드를 천천히 읽어보시면 이해가 더 빠를 듯합니다.

 

그런데 한 가지 아쉬운 점이 있다면

왜? 에 대해 답을 할 수 없는 부분일 것이다.

회전하는 캘리퍼스 알고리즘을 살펴보면 결국 전수 조사해야 하는 O(n^2)에서 필요 없는 부분을 쳐낸, 즉 최장거리가 될 유력한 후보들만 검사해서 시간 복잡도를 줄인다는 거는 알겠는데, 

왜 회전하는 방향이랑 반대방향의 벡터가 되는 순간의 두 점이 후보인지 증명한 글을 찾아볼 수 없었다..

 

어쩔 수 없지만 그런가 보다 하고 외우는 수밖에..

 

5. 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

struct Point
{
	int x, y, p, q;

	Point() {}
	Point(int x_, int y_, int p_ = 0, int q_ = 0) :x(x_), y(y_), p(p_), q(q_) {}

	bool operator < (const Point& arg)
	{
		if (1LL * p*arg.q != 1LL * q*arg.p)	return 1LL * p*arg.q - 1LL * q*arg.p > 0;
		if (y != arg.y)	return y < arg.y;
		return x < arg.x;
	}
};
//a->b, a->b
long long ccw(const Point& a, const Point &b, const Point &c)
{
	return 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);
}
long long cal_dist(const Point& a, const Point& b)
{
	return 1LL*(b.x - a.x)*(b.x - a.x) + 1LL*(b.y - a.y)*(b.y - a.y);
}
int main()
{
	int t;
	scanf("%d", &t);

	while (t--)
	{
		int n;
		vector<Point> v;
		stack<int> s;

		scanf("%d", &n);
		v.resize(n);

		for (int i = 0; i < n; ++i)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			v[i] = Point(x, y);
		}
		sort(v.begin(), v.end());

		for (int i = 1; i < n; ++i)
		{
			v[i].p = v[i].x - v[0].x;
			v[i].q = v[i].y - v[0].y;
		}
		sort(++v.begin(), v.end());

		//make convex hull
		s.push(0);
		s.push(1);
		int next = 2;
		while (next < n){
			while (s.size() >= 2){
				int second, first;
				second = s.top(); s.pop();
				first = s.top();
				if (ccw(v[first], v[second], v[next]) > 0){
					s.push(second);
					break;
				}
			}
			s.push(next++);
		}
		
		//finished.
		vector<Point> convexhull;
		while (!s.empty())
		{
			convexhull.push_back(v[s.top()]);
			s.pop();
		}
		
		long long maxdist = 0;
		Point ans1, ans2;
		int j = 1;
		
		for (int i = 0; i < convexhull.size(); ++i)
		{
			int i_next = (i + 1) % convexhull.size(); 
			for (;;){
				int j_next = (j + 1) % convexhull.size();	
				Point v_i, v_j;	

				v_i.x = convexhull[i_next].x - convexhull[i].x;
				v_i.y = convexhull[i_next].y - convexhull[i].y;

				v_j.x = convexhull[j_next].x - convexhull[j].x;
				v_j.y = convexhull[j_next].y - convexhull[j].y;
				
				Point temp = Point(0,0);	

				if (ccw(temp, v_i, v_j) < 0)	//시계 반대방향으로 돌기 때문에. 가변적임.
					j = j_next;
				else 
					break;
			}
			long long dist = cal_dist(convexhull[i], convexhull[j]);

			if (dist > maxdist)
			{
				maxdist = dist;
				ans1 = convexhull[i];
				ans2 = convexhull[j];
			}
		}

		printf("%d %d %d %d\n", ans1.x, ans1.y, ans2.x, ans2.y);
	}
	return 0;
}

 

 

6. 결과

 

지적, 댓글 언제나 환영입니다. :)