NYPC2024 문제 - 루시드의 레이저 공격을 피해라

NYPC2024 루시드의 레이저 공격을 피해라 문제 풀이를 진행하였습니다.
NYPC문제는 BIKO를 통하여 풀었습니다

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

2차원 공간의 크기를 나타내는 정수 N, 레이저의 수 M, 쿼리의 수 Q가 주어집니다.
2차원 공간의 (x1,y1)위치에 있고 (x2,y2)위치로 이동하려고 하며 반드시 x축이나 y축에 평행하게 이동해야 하는 것은 아니다.
이동 과정에서 레이저는 지나갈 수 없으며, 시작점이나 도착점에 레이저가 있는 경우도 불가능하다.
레이저는 두 점을 지나가는 무한히 긴 직선이며 수직이거나 수평이거나 기울기가 45도로 기울어진 대각선이다.
레이저는 총 M번 쏘고, 사라지지 않습니다.
시작점(x1,y1)과 도착점(x2,y2)로 이루어진 쿼리 Q개가 주어졌을 때 시작점에서 도착점으로 이동 가능한지 판별하는 프로그램을 작성해라.

문제 풀이

레이저의 모형은 총 4가지로 수직, 수평, 45도, -45(135도)로 이루어져 있습니다.
시작점에서 도착점으로 이동이 불가능한 경우는 레이저가 시작점과 도착점 사이를 이어지게 될 경우 이동이 불가능해집니다.
이를 확인하는 방법은 여러 가지가 존재하며, 저는 좌표의 절편을 사용하여 판단하였습니다.

1. 한 레이저와 같은 모양으로 시작 지점과 도착 지점을 지나는 레이저를 그려줍니다.
2. 새로 그려진 레이저에서 x절편이나 y절편 중 한가지를 선택하여 구해줍니다.
3. 기존이 있던 레이저의 절편을 구한 후, 두 절편 사이에 기존 레이저의 절편이 있다면 이동이 불가능한 상태임을 알 수 있습니다.

레이저의 수와 쿼리의 수가 너무 많기 때문에 각 모형에 레이저의 데이터를 저장해준 후, 이분탐색을 통해 가능한지 확인해주면 실행시간을 대폭 줄일 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int N, M, Q;
vector<int> wLaser, hLaser, laser1, laser2;

int solve(int x1, int y1, int x2, int y2)
{
	int high, low, mid;

	//두 점이 가로로 평행할 때
	int start = y1 < y2 ? y1 : y2;
	int end = y1 > y2 ? y1 : y2;

	high = hLaser.size()-1;
	low = 0;

	while (high >= low)
	{
		mid = (high + low) / 2;

		if (start <= hLaser[mid] && hLaser[mid] <= end)
			return 0;

		if (start > hLaser[mid])
			low = mid+1;
		else
			high = mid - 1;
	}

	//두 점이 세로로 평행할 때
	start = x1 < x2 ? x1 : x2;
	end = x1 > x2 ? x1 : x2;

	high = wLaser.size() - 1;
	low = 0;

	while (high >= low)
	{
		mid = (high + low) / 2;

		if (start <= wLaser[mid] && wLaser[mid] <= end)
			return 0;

		if (start > wLaser[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}
	
    //대각선으로 존재할 때
	high = laser1.size() - 1;
	low = 0;

	while (high >= low)
	{
		mid = (high + low) / 2;

		int ylaser1 = y1 - x1;
		int ylaser2 = y2 - x2;

		if (ylaser1 < ylaser2)
		{
			if (ylaser1 <= laser1[mid] && laser1[mid] <= ylaser2)
				return 0;
		}
		else
		{
			if (ylaser2 <= laser1[mid] && laser1[mid] <= ylaser1)
				return 0;
		}

		if (ylaser1 > laser1[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}

	high = laser2.size() - 1;
	low = 0;

	while (high >= low)
	{
		mid = (high + low) / 2;

		int ylaser1 = y1 + x1;
		int ylaser2 = y2 + x2;

		if (ylaser1 < ylaser2)
		{
			if (ylaser1 <= laser2[mid] && laser2[mid] <= ylaser2)
				return 0;
		}
		else
		{
			if (ylaser2 <= laser2[mid] && laser2[mid] <= ylaser1)
				return 0;
		}

		if (ylaser1 > laser2[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}

	return 1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> Q;

	int x1, y1, x2, y2;
	
    //각 모형대로 데이터 저장
	for (int i = 0; i < M; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;

		if (x1 == x2)
			wLaser.push_back(x1);
		else if (y1 == y2)
			hLaser.push_back(y1);
		else if (x1 - y1 == x2 - y2)
			laser1.push_back(y1 - x1);
		else
			laser2.push_back(y1 + x1);
	}
	
    //이분탐색을 위한 정렬
	sort(wLaser.begin(), wLaser.end());
	sort(hLaser.begin(), hLaser.end());
	sort(laser1.begin(), laser1.end());
	sort(laser2.begin(), laser2.end());

	for (int i = 0; i < Q; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		cout << solve(x1, y1, x2, y2) << endl;
	}

    return 0;
}

출저

https://www.biko.kr/problem/4711