Python Coding Test Course, Exploring Geometry

Hello! Today, we will learn how to solve geometric problems that are frequently asked in Python coding tests. Geometric problems mainly include calculations of areas, perimeters, intersections, distances, etc., and are an important part of algorithm problem-solving. In this course, we will explain commonly asked problems based on basic geometric concepts and look at step-by-step approaches to successfully solve them.

Problem: Determine if two line segments intersect

This problem involves determining whether two given line segments intersect.

Problem Definition

Determine whether the given two line segments AB and CD intersect. Each line segment is defined by two points as follows:

  • Line segment AB: Point A(x1, y1), Point B(x2, y2)
  • Line segment CD: Point C(x3, y3), Point D(x4, y4)

Input Format

Four integers x1, y1, x2, y2, x3, y3, x4, y4 are given.

Output Format

If the segments intersect, print “YES”. Otherwise, print “NO”.

Problem Approach

To determine whether two line segments intersect, we must use the geometric concept of ‘direction of the segments’. By calculating the direction for each point of the two segments, we can verify whether they intersect.

1. Direction Calculation

To calculate the direction for line segments AB and CD, we use the following formula:

def direction(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px)

This function calculates the direction for points P, Q, R and returns a positive, negative, or zero value.

2. Intersection Determination

We can determine that line segments AB and CD intersect when the endpoints have different directions. That is, the following conditions must be satisfied:

  • The product of direction(A, B, C) and direction(A, B, D) is greater than 0, and the product of direction(C, D, A) and direction(C, D, B) is also greater than 0.

These conditions can be combined to integrate the entire logic into one function.

3. Code Implementation

Let’s implement the entire code based on what we have explained so far.

def ccw(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px) > 0

def is_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
    d1 = ccw(x1, y1, x2, y2, x3, y3)
    d2 = ccw(x1, y1, x2, y2, x4, y4)
    d3 = ccw(x3, y3, x4, y4, x1, y1)
    d4 = ccw(x3, y3, x4, y4, x2, y2)

    if d1 != d2 and d3 != d4:
        return "YES"

    return "NO"

# Example input
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

print(is_intersect(x1, y1, x2, y2, x3, y3, x4, y4))

Conclusion

In this lecture, we implemented an algorithm to determine whether two line segments intersect. Geometric problems are based on basic mathematical theories, and understanding algorithms is necessary. By practicing with various examples, you will gain confidence in solving geometric problems. I hope you will encounter more algorithm problems in the future and improve your coding skills through them.

Thank you!