Advertisement
Guest User

Untitled

a guest
May 28th, 2015
250
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5.  
  6. int sq(int a){
  7. return a*a;
  8. }
  9. bool hitTower(vector<vector<int>> beacon, int start, int end){
  10.  
  11. vector<int> initial = beacon[start];
  12.  
  13. //base case
  14. if(sq(initial[0] - beacon[end][0]) +
  15. sq(initial[1] - beacon[end][1]) <=
  16. sq(initial[2])){
  17. return true;
  18. }
  19.  
  20. //get current beacon out of array
  21. if(start < end)
  22. end--;
  23. beacon.erase(beacon.begin()+start);
  24.  
  25. for(size_t i = 0; i < beacon.size(); i++){
  26. if(sq(initial[0] - beacon[i][0]) +
  27. sq(initial[1] - beacon[i][1]) <=
  28. sq(initial[2])){
  29. return hitTower(beacon, i, end);
  30. }
  31. }
  32. return false;
  33. }
  34.  
  35.  
  36. int main()
  37. {
  38. int b, q;
  39. cin >> b >> q;
  40. vector<vector<int>> beacon(b, vector<int> (3, 0));
  41. vector<bool>hit (b, true);
  42. //grab list of beacons
  43. for(int i = 0; i < b; i++){
  44. cin >> beacon[i][0] >> beacon[i][1] >> beacon[i][2];
  45. }
  46. //check if each query hits tower
  47. for(int i = 0; i < q; i++){
  48. int first, second;
  49. cin >> first >> second;
  50. //adjust value for array indices
  51. first--;
  52. second--;
  53. //hit check
  54. hit[i] = hitTower(beacon, first, second);
  55. }
  56. for(int i = 0; i < q; i++){
  57. if(hit[i]){
  58. cout << "YES" << endl;
  59. }else{
  60. cout << "NO" << endl;
  61. }
  62. }
  63.  
  64.  
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement