[TopCoder] CirclesCountry (원형 국가)
2023. 3. 1. 18:00ㆍAlgorithm
서클스 컨트리는 여러 개의 원형 지역을 포함하는 나라입니다. 일부 구역은 다른 구역 안에 위치할 수 있지만, 그 경계는 교차하거나 닿지 않는다. 카탐은 서클스 컨트리의 주민이다. 그가 두 지역을 오갈 때, 그는 보통 국경을 넘는 것이 힘든 일이기 때문에 가능한 한 가장 적은 수의 지역 경계를 넘으려고 노력한다.
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)
(be sure your method is public)
Examples
0)
{0}
{0}
{2}
-5
1
5
1
Returns: 0
1)
{0,-6,6}
{0,1,2}
{2,2,2}
-5
1
5
1
Returns: 2
2)
{1,-3,2,5,-4,12,12}
{1,-1,2,5,5,1,1}
{8,1,2,1,1,1,2}
-5
1
12
1
Returns: 3
3)
{-3,2,2,0,-4,12,12,12}
{-1,2,3,1,5,1,1,1}
{1,3,1,7,1,1,2,3}
2
3
13
2
Returns: 5
4)
{-107,-38,140,148,-198,172,-179,148,176,153,-56,-187}
{175,-115,23,-2,-49,-151,-52,42,0,68,109,-174}
{135,42,70,39,89,39,43,150,10,120,16,8}
102
16
19
-108
Returns: 3
수학적 사고가 필요한 문제이다.
문제의 목적은 '가장 최소로 넘는 원의 경계 수'이므로 출발지에서 목적지까지 각자가 속한 다른 원들의 개수를 반환하게
하면 된다.
#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();
각 목록 벡터의 차집합을 구하면 해당 원들이 반드시 넘어야할 원들의 목록이다.
'Algorithm' 카테고리의 다른 글
[TopCoder] CantorDust (칸토어 분진) (0) | 2023.03.05 |
---|---|
[TopCoder] HamiltonPath (해밀턴 패스) (0) | 2023.03.01 |
[TopCoder] AutoLoan (자동차 할부) (0) | 2023.03.01 |
[TopCoder] Batchsystem(배치 시스템) (0) | 2023.03.01 |
[TopCoder] StockHistory (주식 히스토리) (0) | 2023.03.01 |