BOJ 1004 - 어린 왕자
알고리즘/수학문제
https://www.acmicpc.net/problem/1004
풀이
문제를 요약하자면 시작점과 도착점의 좌표가 주어지고, 여러 원의 좌표와 반지름이 주어질때 시작점에서 도착점까지 도달하는데 최소로 원을 통과하는 횟수를 출력해야 하는 문제이다.
만약 임의의 원 C에 대해 시작점과 도착점이 둘다 안쪽에 있거나 바깥쪽에 있는 경우에는 해당 원을 거칠 필요가 없다는 뜻이므로 카운팅하지 않아도 된다. 즉, 시작점이 안쪽에 있고 도착점이 바깥쪽에 있거나 그 반대의 경우에만 카운팅을 해주면 최소 횟수를 구할수가 있는데 좌표 P가 C 내부에 있는지 이는 피타고라스의 정리를 사용하여 쉽게 판별할수있다.
$ (x - Cx)^2 + (y - Cy)^2 < Cr^2 $
우리는 시작점과 도착점이 서로 다를 경우에만 카운팅을 해주면 되므로 두 점을 판별한 결과값의 xor 연산 결과가 참일때만 카운트 해주면 된다.
#include <stdio.h> int isInCircle(int x,int y, int Cx, int Cy, int Cr){ return (x-Cx)*(x-Cx) +(y-Cy)*(y-Cy)<Cr*Cr; } int main(){ int t,i; scanf("%d",&t); while(t--){ int x1,y1,x2,y2,n,cx,cy,r,c=0; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n); for(i=0;i<n;i++){ scanf("%d%d%d",&cx,&cy,&r); c += isInCircle(x1,y1,cx,cy,r) ^ isInCircle(x2,y2,cx,cy,r); } printf("%d\n",c); } }