1004

어린 왕자

 

딱 봤을 때는 어려워 보였는데 조금 생각해보니까 풀 수 있었다.

 

시작 좌표와 끝 좌표가 속한 원의 개수를 세주었다.

만약 한 원에 시작 좌표와 끝 좌표가 둘 다 속해 있다면 그 원은 세지 않음. 이를 위해 집합을 사용해 주었다.

또한 집합에 행성의 x,y,r 좌표를 묶어서 저장해주려고 튜플을 이용주었다.

pair로는 두개까지만 묶인다더라..

 

좌표가 원 내부에 있는지 판단해야하는데 처음에 사각형의 내부로 판단해 틀렸었음.

#include<set>
#include<iostream>
#include<tuple>
#include<cmath>
using namespace std;

set<tuple<int, int, int>>P;
set<tuple<int, int, int>>via;

void planet(int a, int b, int r) {
	P.insert(make_tuple(a, b, r));
}

void search(int a, int b ,int c,int d) {
	for (auto i = P.begin();i != P.end();i++) {
		int x = get<0>(*i);
		int y = get<1>(*i);
		int r = get<2>(*i);
		if (pow(a - x, 2) + pow(b - y, 2) < pow(r, 2)) {
			if ( pow(c - x, 2) + pow(d - y, 2) < pow(r, 2)) {
				continue;
			}
			else {
				via.insert(make_tuple(x, y, r));
			}
		}
		else {
			if (pow(c - x, 2) + pow(d - y, 2) < pow(r, 2)) {
				via.insert(make_tuple(x, y, r));
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int start_x, start_y, end_x, end_y, a, b, r;
	int n, m;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> start_x >> start_y >> end_x >> end_y;
		cin >> m;
		for (int j = 0;j < m;j++) {
			cin >> a >> b >> r;
			planet(a, b, r);
		}
		search(start_x, start_y, end_x, end_y);
		int count = via.size();
		cout << count<<"\n";
		P.clear();
		via.clear();
	}
	return 0;
}