Given four co-ordinates A, B, C and D where towers need to be constructed, the task is to check if the tower of sight issue occurs or not.
Tower of sight issue occurs if the towers at A or C lies in the line joining B and D or vice versa.
Examples:
Input: A = (0, 0), B = (0, -2), C = (2, 0), D = (0, 2)
Output: Yes
Explanation:
Tower A lies in the line joining B and D.
Input: A = (0, 0), B = (0, -2), C = (2, 0), D = (0, -5)
Output: No
Explanation:
No intersection occurs.
Approach:
- If A and C are parallel to the X-axis, check if B or D has y coordinate equal to that of A and C and x coordinate in between that of A and C.
- If A and C are parallel to the Y-axis, check if B or D has x coordinate equal to that of A and C and y coordinate in between that of A and C.
- Otherwise, check if B or D satisfies the line equation of A and C.
- Similarly follow the above three steps to check if A or C lies in between B or D.
Below code is the implementation of the above approach:
C++
// C++ program to check if tower// of sight issue occurs or not#include <bits/stdc++.h>using namespace std;// Function to check if point p lies in// between the line joining p1 and p2int checkIntersection(pair<int, int> p1, pair<int, int> p2, pair<int, int> p){ int val; // If parallel to X-axis if (p1.second == p2.second && p1.second == p.second) { if (p.first <= max(p1.first, p2.first) && (p.first >= min(p1.first, p2.first))) // Point p lies between p1 and p2 return 1; } // If parallel to Y-axis if (p1.first == p2.first && p1.first == p.first) { if (p.second <= max(p1.second, p2.second) && (p.second >= min(p1.second, p2.second))) // Point p lies between p1 and p2 return 1; } // If point p satisfies the equation // of line joining p1 and p2 else { val = (p.second - p1.second) * (p2.first - p1.first) - (p.first - p1.first) * (p2.second - p1.second); if (val == 0) if ((p.first <= max(p1.first, p2.first) && (p.first >= min(p1.first, p2.first))) && (p.second <= max(p1.second, p2.second) && (p.second >= min(p1.second, p2.second)))) return 1; } return 0;}// Function to check if tower// of sight issue occurredvoid towerOfSight(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> d){ int flag = 0; if (checkIntersection(a, c, b)) // B lies between AC flag = 1; else if (checkIntersection(a, c, d)) // D lies between AC flag = 1; else if (checkIntersection(b, d, a)) // A lies between BD flag = 1; else if (checkIntersection(b, d, c)) // C lies between BD flag = 1; flag ? cout << "Yes\n" : cout << "No\n";}// Driver codeint main(){ // Point A pair<int, int> a = { 0, 0 }; // Point B pair<int, int> b = { 0, -2 }; // Point C pair<int, int> c = { 2, 0 }; // Point D pair<int, int> d = { 0, 2 }; towerOfSight(a, b, c, d); return 0;} |
Java
// Java program to check if tower// of sight issue occurs or notclass GFG{static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check if point p lies in// between the line joining p1 and p2static int checkIntersection(pair p1, pair p2, pair p){ int val; // If parallel to X-axis if (p1.second == p2.second && p1.second == p.second) { if (p.first <= Math.max(p1.first, p2.first) && (p.first >= Math.min(p1.first, p2.first))) // Point p lies between p1 and p2 return 1; } // If parallel to Y-axis if (p1.first == p2.first && p1.first == p.first) { if (p.second <= Math.max(p1.second, p2.second) && (p.second >= Math.min(p1.second, p2.second))) // Point p lies between p1 and p2 return 1; } // If point p satisfies the equation // of line joining p1 and p2 else { val = (p.second - p1.second) * (p2.first - p1.first) - (p.first - p1.first) * (p2.second - p1.second); if (val == 0) if ((p.first <= Math.max(p1.first, p2.first) && (p.first >= Math.min(p1.first, p2.first))) && (p.second <= Math.max(p1.second, p2.second) && (p.second >= Math.min(p1.second, p2.second)))) return 1; } return 0;} // Function to check if tower// of sight issue occurredstatic void towerOfSight(pair a, pair b, pair c, pair d){ int flag = 0; if (checkIntersection(a, c, b) == 1) // B lies between AC flag = 1; else if (checkIntersection(a, c, d) == 1) // D lies between AC flag = 1; else if (checkIntersection(b, d, a) == 1) // A lies between BD flag = 1; else if (checkIntersection(b, d, c) == 1) // C lies between BD flag = 1; System.out.print(flag==1?"Yes\n":"No\n");} // Driver codepublic static void main(String[] args){ // Point A pair a = new pair( 0, 0 ); // Point B pair b = new pair( 0, -2 ); // Point C pair c = new pair( 2, 0 ); // Point D pair d = new pair( 0, 2 ); towerOfSight(a, b, c, d); }}// This code is contributed by Rajput-Ji |
Python3
# Python 3 program to check if tower# of sight issue occurs or not # Function to check if point p lies in# between the line joining p1 and p2def checkIntersection(p1,p2,p): # If parallel to X-axis if (p1[1] == p2[1] and p1[1] == p[1]): if (p[0] <= max(p1[0], p2[0]) and (p[0] >= min(p1[0], p2[0]))): # Point p lies between p1 and p2 return 1 # If parallel to Y-axis if (p1[0] == p2[0] and p1[0] == p[0]): if (p[1] <= max(p1[1], p2[1]) and (p[1] >= min(p1[1], p2[1]))): # Point p lies between p1 and p2 return 1 # If point p satisfies the equation # of line joining p1 and p2 else : val = ((p[1] - p1[1])*(p2[0] - p1[0]) - (p[0] - p1[0]) * (p2[1] - p1[1])) if (val == 0): if ((p[0] <= max(p1[0], p2[0]) and (p[0] >= min(p1[0], p2[0]))) and (p[1] <= max(p1[1], p2[1]) and (p[1] >= min(p1[1], p2[1])))): return 1 return 0 # Function to check if tower# of sight issue occurreddef towerOfSight(a, b, c, d): flag = 0 if (checkIntersection(a, c, b)): # B lies between AC flag = 1 elif (checkIntersection(a, c, d)): # D lies between AC flag = 1 elif (checkIntersection(b, d, a)): # A lies between BD flag = 1 elif (checkIntersection(b, d, c)): # C lies between BD flag = 1 if(flag): print("Yes") else: print("No") # Driver codeif __name__ == "__main__": # Point A a = [ 0, 0 ] # Point B b = [ 0, -2 ] # Point C c = [ 2, 0 ] # Point D d = [ 0, 2 ] towerOfSight(a, b, c, d) # This code is contributed by chitranayal |
C#
// C# program to check if tower// of sight issue occurs or notusing System;class GFG{ class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check if point p lies in// between the line joining p1 and p2static int checkIntersection(pair p1, pair p2, pair p){ int val; // If parallel to X-axis if (p1.second == p2.second && p1.second == p.second) { if (p.first <= Math.Max(p1.first, p2.first) && (p.first >= Math.Min(p1.first, p2.first))) // Point p lies between p1 and p2 return 1; } // If parallel to Y-axis if (p1.first == p2.first && p1.first == p.first) { if (p.second <= Math.Max(p1.second, p2.second) && (p.second >= Math.Min(p1.second, p2.second))) // Point p lies between p1 and p2 return 1; } // If point p satisfies the equation // of line joining p1 and p2 else { val = (p.second - p1.second) * (p2.first - p1.first) - (p.first - p1.first) * (p2.second - p1.second); if (val == 0) if ((p.first <= Math.Max(p1.first, p2.first) && (p.first >= Math.Min(p1.first, p2.first))) && (p.second <= Math.Max(p1.second, p2.second) && (p.second >= Math.Min(p1.second, p2.second)))) return 1; } return 0;} // Function to check if tower// of sight issue occurredstatic void towerOfSight(pair a, pair b, pair c, pair d){ int flag = 0; if (checkIntersection(a, c, b) == 1) // B lies between AC flag = 1; else if (checkIntersection(a, c, d) == 1) // D lies between AC flag = 1; else if (checkIntersection(b, d, a) == 1) // A lies between BD flag = 1; else if (checkIntersection(b, d, c) == 1) // C lies between BD flag = 1; Console.Write(flag==1?"Yes\n":"No\n");} // Driver codepublic static void Main(String[] args){ // Point A pair a = new pair( 0, 0 ); // Point B pair b = new pair( 0, -2 ); // Point C pair c = new pair( 2, 0 ); // Point D pair d = new pair( 0, 2 ); towerOfSight(a, b, c, d); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to check if tower// of sight issue occurs or not// Function to check if point p lies in// between the line joining p1 and p2function checkIntersection(p1,p2,p){ let val; // If parallel to X-axis if (p1[1] == p2[1] && p1[1] == p[1]) { if (p[0] <= Math.max(p1[0], p2[0]) && (p[0] >= Math.min(p1[0], p2[0]))) // Point p lies between p1 and p2 return 1; } // If parallel to Y-axis if (p1[0] == p2[0] && p1[0] == p[0]) { if (p[1] <= Math.max(p1[1], p2[1]) && (p[1] >= Math.min(p1[1], p2[1]))) // Point p lies between p1 and p2 return 1; } // If point p satisfies the equation // of line joining p1 and p2 else { val = (p[1] - p1[1]) * (p2[0] - p1[0]) - (p[0] - p1[0]) * (p2[1] - p1[1]); if (val == 0) if ((p[0] <= Math.max(p1[0], p2[0]) && (p[0] >= Math.min(p1[0], p2[0]))) && (p[1] <= Math.max(p1[1], p2[1]) && (p[1] >= Math.min(p1[1], p2[1])))) return 1; } return 0;}// Function to check if tower// of sight issue occurredfunction towerOfSight(a,b,c,d){ let flag = 0; if (checkIntersection(a, c, b) == 1) // B lies between AC flag = 1; else if (checkIntersection(a, c, d) == 1) // D lies between AC flag = 1; else if (checkIntersection(b, d, a) == 1) // A lies between BD flag = 1; else if (checkIntersection(b, d, c) == 1) // C lies between BD flag = 1; document.write(flag==1?"Yes\n":"No\n");}// Driver code// Point Alet a=[0,0];// Point Blet b=[0, -2 ];// Point Clet c=[2, 0 ];// Point Dlet d=[0, 2];towerOfSight(a, b, c, d);// This code is contributed by avanitrachhadiya2155</script> |
Output:
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
