서클스 컨트리는 여러 개의 원형 지역을 포함하는 나라입니다. 일부 구역은 다른 구역 안에 위치할 수 있지만, 그 경계는 교차하거나 닿지 않는다. 카탐은 서클스 컨트리의 주민이다. 그가 두 지역을 오갈 때, 그는 보통 국경을 넘는 것이 힘든 일이기 때문에 가능한 한 가장 적은 수의 지역 경계를 넘으려고 노력한다.
Circles Country를 무한한 비행기로 상상해 보세요. 여기서 (X[i], Y[i]는 i번째 구역의 중심 좌표이고 R[i]는 반지름입니다. Qatam은 현재 포인트(x1,y1)에 있으며 포인트(x2,y2)에 도달해야 합니다. 이 두 지점 모두 지역 경계에 있지 않다. 목적지에 도달하기 위해 통과해야 하는 최소 구역 경계를 반환합니다.
Definition
Class:
CirclesCountry
Method:
leastBorders
Parameters:
vector <int>, vector <int>, vector <int>, int, int, int, int
Returns:
int
Method signature:
int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2)
문제의 목적은 '가장 최소로 넘는 원의 경계 수'이므로 출발지에서 목적지까지 각자가 속한 다른 원들의 개수를 반환하게
하면 된다.
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class CirclesCountry{
public:
bool isInsideCircle(int centerX, int centerY, int R, int x, int y){
// 좌표 x, y가 특정 circle에 포함되는지 여부를 체크
double distance = sqrt((centerX-x)*(centerX-x) + (centerY-y)*(centerY-y));
if(distance <= R){
return true;
}
else
return false;
}
먼저 원의 좌표, 반지름 길이와 특정 좌표를 입력받아 이 좌표가 해당 원 안에 들어있는지는 판단하는 함수를 구현하였다.
int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2){
vector<int> circOfDep; //출발지가 속한 원들
vector<int> circOfArr; //목적지가 속한 원들
for(int i=0; i<X.size(); i++){
if(isInsideCircle(X[i], Y[i], R[i], x1, y1)){
circOfDep.push_back(i);
//출발지 좌표가 속한 원들 목록을 만든다.
}
if(isInsideCircle(X[i], Y[i], R[i], x2, y2)){
circOfArr.push_back(i);
//목적지 좌표가 속한 원들 목록을 만든다.
}
}
그리고 구현한 함수를 활용하여 출발지, 목적지 좌표가 속해있는 각각의 원들의 목록(index)을 생성한다.
vector<int> result;
set_symmetric_difference(circOfDep.begin(),circOfDep.end(), circOfArr.begin(), circOfArr.end(),back_inserter(result));
// 출발지, 목적지 좌표가 속한 원들의 차집합이 넘어야할 최소 경계수이다.
return result.size();
