당신은 어떤 임무를 수행해야 한다. 그 임무는 무한히 펼쳐진 2차원 격자판 위의 출발 지점 (sx, sy) 에 요원을 보내, 적 진영에 발각되지 않도록 이동을 서포트해서, 적의 기지인 (gx, gy) 에 무사히 잠입시키는 것이다. 당신은 이 중요한 임무의 잠입요원 역을 잠입의 달인 A에게 부탁했다.
A는 상하좌우 인접한 칸으로의 이동을 반복하여 적의 기지로 향한다. 또한, 신속하게 임무를 수행하기 위해 출발 지점에서 적의 기지까지 반드시 최단거리로 이동한다.
사전에 정찰을 한 결과, 2차원 격자판 위에는 적의 센서가 N개 존재하고, i번째 센서는 (xi, yi) 를 중심으로 한 변의 길이가 2ri + 1 인 정사각형 영역, 즉 |x - xi| ≤ ri , |y - yi| ≤ ri 을 만족하는 모든 칸 (x, y) 를 감지할 수 있다. A는 한 개 이상의 센서가 감지할 수 있는 영역에 들어가게 되면 적에게 발각된다.
이 때, 현재 센서의 위치에 따라 A가 최단거리로 적의 기지에 이동할 수 없는 경우가 있을 수도 있다. 이 경우에는 서포트 역인 당신이 센서를 부숴줘야 한다. 당신은 위험을 줄이기 위해 부수는 센서의 개수를 최소화하려고 한다.
출발 지점과 적의 기지의 위치, 그리고 센서들의 정보가 주어질 때, A가 출발 지점에서 적의 기지까지 최단거리로 이동할 수 있도록 부숴야 하는 센서의 개수의 최솟값을 구하여라.
예를 들어, 예제 1번의 4번째 테스트 케이스는 아래의 왼쪽 그림처럼 나타낼 수 있다. 왼쪽 위 원이 출발 지점, 오른쪽 아래 원이 적의 기지, 붉은 점과 정사각형이 센서와 그 센서가 감지할 수 있는 영역이다. 아래의 오른쪽 그림과 같이 3개의 센서를 부수면 A는 적의 기지까지 최단거리로 이동할 수 있다. 3개 미만의 센서를 부숴서 적의 기지까지 최단거리로 이동할 수 없으므로 답은 3이 된다.
ㅤ
입력
입력은 최대 100개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
첫번째 줄에는 센서의 개수 N이 주어진다. (1 ≤ N ≤ 105)
두번째 줄에는 sx, sy, gx, gy 가 공백으로 구분되어 주어지며, 이들은 출발 지점 (sx, sy) 와 적의 기지의 위치 (gx, gy) 를 나타낸다.이 때, (sx, sy) 와 (gx, gy) 는 서로 다르다. (1 ≤ sx, gx ≤ 1000,1 ≤ sy, gy ≤ 1000)
다음 N개의 줄의 i번째 줄에는 i번째 센서의 정보 xi, yi, ri 가 공백으로 구분되어 주어지며, 이들은 센서가 (xi, yi) 을 중심으로 한 변의 길이가 2ri +1 인 정사각형 영역을 감지할 수 있다는 것을 나타낸다. (1 ≤ xi ≤ 1000,1 ≤ yi ≤ 1000,0 ≤ ri ≤ 1000)
입력으로 주어지는 모든 수는 정수이며, 입력의 마지막에는 0 하나가 주어진다.
(입력 제한이 부족한 것 같아서 대회 입력을 찾아본 결과, 입력 파일은 4개 있고, 각 입력 파일 당 약 30만줄 정도 들어옵니다.)
ㅤ
출력
각 테스트 케이스에 대해, A가 (sx, sy) 에서 (gx, gy) 까지 센서에 감지되지 않고 최단거리로 이동할 수 있도록 부숴야 하는 센서의 개수의 최솟값을 한 줄에 하나씩 출력한다.
ㅤ
ㅤ
ㅤ
ㅤ
※※※
문제 지문의 마지막 문단에 센서를 부수지 않으면 적의 기지에 잠입할 수 없는 잠입의 달인 A보다, 적에게 들키지 않으면서 센서를 부술 수 있는 여러분이 더 잠입 스킬이 뛰어난 거 아니냐 하는 분들을 위한 여담이 있습니다. 사실 A는 잠입의 달인이 아니라 자신이 잠입의 달인이라고 착각하고 있는 일반인이고, 여러분이 누군가를 잠입시키는 것의 달인이라고 합니다. 적에게 뿐만 아니라 A에게까지 들키지 않으면서 센서를 부수고, A가 자신이 잠입의 달인이라고 생각하게 만드는 것으로, 여러분은 자신의 능력에 대한 긍지를 느끼고 있다고 하네요.
cinador 3년 전
문제
당신은 어떤 임무를 수행해야 한다. 그 임무는 무한히 펼쳐진 2차원 격자판 위의 출발 지점 (sx, sy) 에 요원을 보내, 적 진영에 발각되지 않도록 이동을 서포트해서, 적의 기지인 (gx, gy) 에 무사히 잠입시키는 것이다. 당신은 이 중요한 임무의 잠입요원 역을 잠입의 달인 A에게 부탁했다.
A는 상하좌우 인접한 칸으로의 이동을 반복하여 적의 기지로 향한다. 또한, 신속하게 임무를 수행하기 위해 출발 지점에서 적의 기지까지 반드시 최단거리로 이동한다.
사전에 정찰을 한 결과, 2차원 격자판 위에는 적의 센서가 N개 존재하고, i번째 센서는 (xi, yi) 를 중심으로 한 변의 길이가 2ri + 1 인 정사각형 영역, 즉 |x - xi| ≤ ri , |y - yi| ≤ ri 을 만족하는 모든 칸 (x, y) 를 감지할 수 있다. A는 한 개 이상의 센서가 감지할 수 있는 영역에 들어가게 되면 적에게 발각된다.
이 때, 현재 센서의 위치에 따라 A가 최단거리로 적의 기지에 이동할 수 없는 경우가 있을 수도 있다. 이 경우에는 서포트 역인 당신이 센서를 부숴줘야 한다. 당신은 위험을 줄이기 위해 부수는 센서의 개수를 최소화하려고 한다.
출발 지점과 적의 기지의 위치, 그리고 센서들의 정보가 주어질 때, A가 출발 지점에서 적의 기지까지 최단거리로 이동할 수 있도록 부숴야 하는 센서의 개수의 최솟값을 구하여라.
예를 들어, 예제 1번의 4번째 테스트 케이스는 아래의 왼쪽 그림처럼 나타낼 수 있다. 왼쪽 위 원이 출발 지점, 오른쪽 아래 원이 적의 기지, 붉은 점과 정사각형이 센서와 그 센서가 감지할 수 있는 영역이다. 아래의 오른쪽 그림과 같이 3개의 센서를 부수면 A는 적의 기지까지 최단거리로 이동할 수 있다. 3개 미만의 센서를 부숴서 적의 기지까지 최단거리로 이동할 수 없으므로 답은 3이 된다.
ㅤ
입력
입력은 최대 100개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
첫번째 줄에는 센서의 개수 N이 주어진다. (1 ≤ N ≤ 105)
두번째 줄에는 sx, sy, gx, gy 가 공백으로 구분되어 주어지며, 이들은 출발 지점 (sx, sy) 와 적의 기지의 위치 (gx, gy) 를 나타낸다. 이 때, (sx, sy) 와 (gx, gy) 는 서로 다르다. (1 ≤ sx, gx ≤ 1000,1 ≤ sy, gy ≤ 1000)
다음 N개의 줄의 i번째 줄에는 i번째 센서의 정보 xi, yi, ri 가 공백으로 구분되어 주어지며, 이들은 센서가 (xi, yi) 을 중심으로 한 변의 길이가 2ri +1 인 정사각형 영역을 감지할 수 있다는 것을 나타낸다. (1 ≤ xi ≤ 1000,1 ≤ yi ≤ 1000,0 ≤ ri ≤ 1000)
입력으로 주어지는 모든 수는 정수이며, 입력의 마지막에는 0 하나가 주어진다.
(입력 제한이 부족한 것 같아서 대회 입력을 찾아본 결과, 입력 파일은 4개 있고, 각 입력 파일 당 약 30만줄 정도 들어옵니다.)
ㅤ
출력
각 테스트 케이스에 대해, A가 (sx, sy) 에서 (gx, gy) 까지 센서에 감지되지 않고 최단거리로 이동할 수 있도록 부숴야 하는 센서의 개수의 최솟값을 한 줄에 하나씩 출력한다.
ㅤ
ㅤ
ㅤ
ㅤ
※※※
문제 지문의 마지막 문단에 센서를 부수지 않으면 적의 기지에 잠입할 수 없는 잠입의 달인 A보다, 적에게 들키지 않으면서 센서를 부술 수 있는 여러분이 더 잠입 스킬이 뛰어난 거 아니냐 하는 분들을 위한 여담이 있습니다. 사실 A는 잠입의 달인이 아니라 자신이 잠입의 달인이라고 착각하고 있는 일반인이고, 여러분이 누군가를 잠입시키는 것의 달인이라고 합니다. 적에게 뿐만 아니라 A에게까지 들키지 않으면서 센서를 부수고, A가 자신이 잠입의 달인이라고 생각하게 만드는 것으로, 여러분은 자신의 능력에 대한 긍지를 느끼고 있다고 하네요.