취미로 코딩하기

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

이번에 볼 문제는 백준 10254번 문제인 고속도로이다.
문제는 아래 링크를 확인하자.

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

주어지는 점들로 convex hull을 구하고, 이를 구성하는 점들 중 가장 먼 두 점을 rotating calipers 알고리즘 등을 이용해 구하는 문제이다.

글쓴이는 convex hull을 Andrew's algorithm을 이용해 구했고, rotating calipus를 두 직선의 기울기의 비교를 정수 자료형의 연산만으로 수행하는 코드를 작성해 문제를 해결했다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int N;
pll points[200000];
vector<pll> upperhull; // leftmost x의 lowermost y부터 rightmost x의 uppermost y까지
vector<pll> lowerhull;

int CCW(pll& A, pll& B, pll& C) {
	ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
	if (ccw > 0) return 1;
	else if (ccw < 0) return -1;
	else return 0;
}

void andrew_algorithm() {
	sort(points, points + N);
	
	//upperhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = upperhull.size();
		while (cursize > 1) {
			auto& L = upperhull[cursize - 2], & M = upperhull[cursize - 1];
			if (CCW(L, M, cur) != -1) upperhull.pop_back(), cursize--;
			else break;
		}
		upperhull.emplace_back(cur);
	}

	//lowerhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = lowerhull.size();
		while (cursize > 1) {
			auto& L = lowerhull[cursize - 2], & M = lowerhull[cursize - 1];
			if (CCW(L, M, cur) != 1) lowerhull.pop_back(), cursize--;
			else break;
		}
		lowerhull.emplace_back(cur);
	}
}

ll dfunc(pll& p1, pll& p2) {
	return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

void rotating_calipers() {
	int u = 0, uend = upperhull.size(), l = lowerhull.size() - 1;
	ll mx = dfunc(upperhull[u], lowerhull[l]), X1 = upperhull[u].first, Y1 = upperhull[u].second, X2 = lowerhull[l].first, Y2 = lowerhull[l].second;
	while (u < uend - 1 && l > 0) {
		if (upperhull[u].first == upperhull[u + 1].first) u++;
		else if (lowerhull[l].first == lowerhull[l - 1].first) l--;
		else {
			ll dx1 = upperhull[u + 1].first - upperhull[u].first, dy1 = upperhull[u + 1].second - upperhull[u].second;
			ll dx2 = lowerhull[l].first - lowerhull[l - 1].first, dy2 = lowerhull[l].second - lowerhull[l - 1].second;

			if (dy1 * dx2 > dx1 * dy2) u++;
			else l--;
		}

		ll tmp = dfunc(upperhull[u], lowerhull[l]);
		if (tmp > mx) mx = tmp, X1 = upperhull[u].first, Y1 = upperhull[u].second, X2 = lowerhull[l].first, Y2 = lowerhull[l].second;
	}

	while (u < uend - 1) {
		u++;
		ll tmp = dfunc(upperhull[u], lowerhull[l]);
		if (tmp > mx) mx = tmp, X1 = upperhull[u].first, Y1 = upperhull[u].second, X2 = lowerhull[l].first, Y2 = lowerhull[l].second;
	}
	while (l > 0) {
		l--;
		ll tmp = dfunc(upperhull[u], lowerhull[l]);
		if (tmp > mx) mx = tmp, X1 = upperhull[u].first, Y1 = upperhull[u].second, X2 = lowerhull[l].first, Y2 = lowerhull[l].second;
	}

	cout << X1 << ' ' << Y1 << ' ' << X2 << ' ' << Y2 << '\n';
}

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

	int T; cin >> T;
	while (T--) {
		upperhull.clear(), lowerhull.clear();
		cin >> N;
		for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
		andrew_algorithm();
		rotating_calipers();
	}
}