Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int sq(int a){
- return a*a;
- }
- bool hitTower(vector<vector<int>> beacon, int start, int end){
- vector<int> initial = beacon[start];
- //base case
- if(sq(initial[0] - beacon[end][0]) +
- sq(initial[1] - beacon[end][1]) <=
- sq(initial[2])){
- return true;
- }
- //get current beacon out of array
- if(start < end)
- end--;
- beacon.erase(beacon.begin()+start);
- for(size_t i = 0; i < beacon.size(); i++){
- if(sq(initial[0] - beacon[i][0]) +
- sq(initial[1] - beacon[i][1]) <=
- sq(initial[2])){
- return hitTower(beacon, i, end);
- }
- }
- return false;
- }
- int main()
- {
- int b, q;
- cin >> b >> q;
- vector<vector<int>> beacon(b, vector<int> (3, 0));
- vector<bool>hit (b, true);
- //grab list of beacons
- for(int i = 0; i < b; i++){
- cin >> beacon[i][0] >> beacon[i][1] >> beacon[i][2];
- }
- //check if each query hits tower
- for(int i = 0; i < q; i++){
- int first, second;
- cin >> first >> second;
- //adjust value for array indices
- first--;
- second--;
- //hit check
- hit[i] = hitTower(beacon, first, second);
- }
- for(int i = 0; i < q; i++){
- if(hit[i]){
- cout << "YES" << endl;
- }else{
- cout << "NO" << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement