티스토리 뷰
풀이법.
필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램.
1) 진입과, 이탈을 최소로 해야하며, 진입/이탈을 최소화할 수 있는 루트는 묻지않았다.
-> 즉, 진입과 이탈을 하는 횟수만 계산하면됨.
2) 진입/이탈을 하는 조건은 시작점->도착점을 지나면서 원을 몇개의 원을 이탈(시작점기준) 몇개의 원을 진입(도착점기준)이다.
-> 다시 말하자면 시작점에서 도착점으로 갈때 반드시 거쳐야하는 원은 몇개인가, 시작점과 도착점이 몇개의 원에 둘러쌓여있는것인가?를 묻는다.
ex) 일반적인경우
2개의 원에 둘러쌓인 시작점, 2개의 원에 둘러쌓인 도착점.
시작점에서 2개의 원을 이탈, 도착점에 도달하기위해 2개의 원에 진입.
* 다른 행성들이 어떻든 상관없다. 문제에서 묻지않았다.
3) 겹칠경우, 교차할경우는 문제에서 제외하므로 추가적으로 예외처리를 해줄 필요가 없다.
문제에서 쉬운 풀이를 위해서 제외한 상황이 많으므로, 매우간단하게 해결가능하다.
문제풀이를 위해 필요한 공식.
http://www.mathsisfun.com/algebra/circle-equations.html
(x−a)^2 + (y−b)^2 = r^2 이므로.
(x−a)^2 + (y−b)^2 < r^2 이면, r범위 이내에 있는 점이 포함하는지 알 수 있다.
이를 적용해보자면,
-> (a,b)는 행성계의 중점. (x,y)는 도착점 혹은 시작점
** 한가지 더, 만약 한 원안에 시작점과 도착점이 모두 포함되어있을경우는? 제외해줘야한다.
즉, 하나의 행성범위안에, 시작점,도착점이 모두 같이있다면 진입/이탈 횟수를 계산해줄 필요가 없다.
진입/이탈 횟수를 계산해줄 필요가 없는경우는,
1) 시작점, 도착점 두점 모두 원 밖에 있을때. (어떤 행성계에도 포함되어있지 않을때)
2) 시작점, 도착점 두점 모두 원 안에 있을때. ( 두 지점 모두 같은 행성계 내에 있을때)
즉 XOR조건일경우에만 count를 해주면 된다.
코드예시
#include <stdio.h>
#include <math.h>
/* C언어에서는 bool type이 없으므로 따로 정의*/
typedef enum
{
false = 0, true = 1
}bool;
/*원안에 포함되어있는지 체크하는 함수 */
bool get_ready(int x,int y, int cx, int cy, int r);
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T ; t++){
int x1, y1, x2, y2, num, count=0;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
scanf("%d", &num);
for (int i=0; i<num; i++){
/* 원안에 몇개가 들어가있는지 검사한다 */
int xt,yt,rt;
scanf("%d %d %d", &xt, &yt, &rt);
/* XOR */
if (get_ready(x1,y1,xt,yt,rt) != get_ready(x2,y2,xt,yt,rt)) {
count ++;
}
}
printf("%d\n", count);
/* 출력값에 \n 빼먹지말자. 삽질함; */
}
return 0;
}
bool get_ready(int x, int y, int cx, int cy, int r) {
if ( (x - cx)*(x - cx) + (y - cy)*(y - cy) > r*r )
return false;
else
return true;
}