취미로 코딩하기

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

이번에 볼 문제는 백준 26276번 문제인 Point in Triangle이다.
문제는 아래 링크를 확인하자.

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

편의상 점 $P$가 원점으로 주어지고, 주어지는 점 중 $x$좌표가 0인 점이 없다고 가정하자. 이 때, 모든 점은 직선 $x=0$에 의해 좌표평면의 왼쪽에 있거나 오른쪽에 있게 된다.

좌표평면의 왼쪽에 있는 점 셋만을 이용하거나 오른쪽에 있는 점 셋만을 이용해서는 원점을 완전히 포함하는 삼각형을 만들 수 없음은 자명하다. 따라서 왼쪽에서 점을 하나, 오른쪽에서 점을 둘 고르는 경우와 왼쪽에서 점을 둘, 오른쪽에서 점을 하나 고르는 경우의 두 가지 경우만을 고려하면 문제를 해결할 수 있다. 이중 한 경우만 해결할 수 있어도 다른 경우 또한 같은 방법으로 해결할 수 있으므로, 아래에서는 오른쪽에서 한 점을 고르는 경우를 생각해보자.

위와 같이 점을 고르려 할 때 오른쪽에서 고른 점을 $X$라 하자. $X$와 원점을 잇는 직선 $l$을 그으면 $l$은 좌표평면의 왼쪽을 위와 아래의 둘로 나누게 된다. ($l$ 위의 점을 포함시켜 세 점을 고른다면 항상 원점을 포함할 수 없으므로 여기에서는 $l$ 위의 점들은 생각하지 않겠다.) 이 때, 좌표평면의 왼쪽에서 $l$의 위쪽에서 두 점을 고르거나 아래쪽에서 두 점을 고르면 구성된 삼각형은 원점을 포함하지 않게 되고 $l$의 위와 아래에서 각각 한 점씩 고르면 구성된 삼각형은 원점을 포함하게 됨을 관찰하자.

이를 모든 점에 대해 빠르게 계산하기 위해 점들을 기울기(각도)를 기준으로 정렬한 뒤 투포인터를 활용해 스위핑(sweeping)해주자.

위 과정에서 각 점과 원점 사이의 거리는 삼각형이 원점을 포함하는지 여부에 영향을 주지 않는다는 점을 관찰하자. 즉, 이 문제를 해결하는 데에 있어서 점의 정보를 저장할 때 거리를 제외한 원점을 기준으로 한 기울기(각도) 정보만을 보관해도 충분하다.

$x$좌표가 0인 점은 주어진 범위의 격자점으로 만들 수 있는 기울기보다 더 큰 기울기(예를 들어 글쓴이의 구현의 경우 2,000,000,007)를 무한대로 삼아 $y$가 0보다 큰 점들과 작은 점들을 각각 왼쪽과 오른쪽 영역으로 따로 집어넣는 처리를 해주자. 이와 같이 처리를 한 뒤에도 기존의 세 점을 이었을 때 삼각형이 원점을 포함했다면 바꾼 후의 세 점을 이어도 원점을 포함하고, 그렇지 않았다면 여전히 원점을 포함하지 않음을 확인하자.

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

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

int N;
ll X, Y;
vector<pll> LEFT, RIGHT;

bool comp(pll& l, pll& r) {
	return l.second * r.first < r.second* l.first;
}

bool comp2(pll& l, pll& r) {
	return l.second * r.first <= r.second * l.first;
}

ll ans;

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

	cin >> N >> X >> Y;
	while (N--) {
		ll x, y; cin >> x >> y;
		ll dx = x - X, dy = y - Y;
		if (dx > 0) RIGHT.emplace_back(make_pair(dx, dy));
		else if (dx < 0) LEFT.emplace_back(make_pair(-dx, -dy));
		else if (dy > 0) RIGHT.emplace_back(make_pair(1, 2000000007));
		else LEFT.emplace_back(make_pair(1, 2000000007));
	}

	sort(LEFT.begin(), LEFT.end(), comp);
	sort(RIGHT.begin(), RIGHT.end(), comp);

	ll idx1 = 0, idx2 = 0, sizeL = LEFT.size();
	for (auto& p : RIGHT) {
		while (idx1 < sizeL && comp(LEFT[idx1], p)) idx1++;
		while (idx2 < sizeL && comp2(LEFT[idx2], p)) idx2++;

		ans += idx1 * (sizeL - idx2);
	}

	idx1 = 0, idx2 = 0; ll sizeR = RIGHT.size();

	for (auto& p : LEFT) {
		while (idx1 < sizeR && comp(RIGHT[idx1], p)) idx1++;
		while (idx2 < sizeR && comp2(RIGHT[idx2], p)) idx2++;

		ans += idx1 * (sizeR - idx2);
	}

	cout << ans;
}