CAKP06 - Editorial

PROBLEM LINK:

Jethalal and Mehta

Author: Suraj Verma and Shreyash Choudhary

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math, Geometry

PROBLEM:

Jethalal is traveling from City A to City B for his Business meeting.

And while onboarding the train, he gets a call from his closest friend Mehta and came to know that Mehta was travelling from City C to City D.

And they decided to meet each other at the station that is common between their respective train’s route.

Imagine the route of the train as a cartesian-co-ordinate system. Your task is to determine whether they can meet or not.

EXPLANATION:

For simplicity, let’s consider the route of each train as a line, and the start point and endpoint as source and destination of their journey respectively.

If the lines are parallel, they will not intersect at any point of time so the answer is NO.
If the lines aren’t parallel, then there are 2 cases:

  • The point of intersection is within the bounds of start point and end points of each source and destination
  • The point of intersection is out of bounds.

If the point of intersection is within the bounds, then the answer will be YES else NO.

SOLUTIONS:

Setter's Solution
t = int(input())

for _ in range(t):
	ax, ay = map(int, input().split())
	bx, by = map(int, input().split())
	cx, cy = map(int, input().split())
	dx, dy = map(int, input().split())

	a1 = ay-by
	b1 = bx-ax
	a2 = cy-dy
	b2 = dx-cx

	c1 = ax*a1+ay*b1
	c2 = cx*a2+cy*b2
	eq = a1*b2-b1*a2

	if(eq == 0):
		print("NO")
		continue

	x = (b2*c1-b1*c2)/eq
	y = (a1*c2-c1*a2)/eq

	if(x <= max(ax, bx) and x >= min(ax, bx) and y <= max(ay, by) and y >= min(ay, by) and y <= max(cy, dy) and y >= min(cy, dy) and x >= min(cx, dx) and x <= max(cx, dx)):
		print("YES")
	else:
		print("NO")