CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:Farah
Submission time:2024-11-11 17:31:55 +0200
Language:C++ (C++20)
Status:COMPILE ERROR

Compiler report

input/code.cpp:24:7: error: invalid preprocessing directive #Close
   24 |     # Close the polygon
      |       ^~~~~
input/code.cpp:38:11: error: invalid preprocessing directive #Check
   38 |         # Check if (px, py) is on segment (x1,y1)-(x2,y2)
      |           ^~~~~
input/code.cpp:42:11: error: invalid preprocessing directive #Now
   42 |         # Now check if px is between x1 and x2, and py between y1 and y2
      |           ^~~
input/code.cpp:52:15: error: invalid preprocessing directive #Check
   52 |             # Check if point is on the edge
      |               ^~~~~
input/code.cpp:56:15: error: invalid preprocessing directive #Check
   56 |             # Check if the ray crosses the edge
      |               ^~~~~
input/code.cpp:57:15: error: invalid preprocessing directive #We
   57 |             # We need to check if the edge crosses the horizontal line at py
      |               ^~
input/code.cpp:58:15: error: invalid preprocessing directive #and
   58 |...

Code

import sys

def main():
    import sys

    import sys

    sys.setrecursionlimit(1 << 25)

    def input():
        return sys.stdin.read()

    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    polygon = []
    for _ in range(n):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        polygon.append( (x, y) )

    # Close the polygon
    edges = []
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1)%n]
        edges.append( (x1, y1, x2, y2) )

    points = []
    for _ in range(m):
        px = int(data[idx]); idx +=1
        py = int(data[idx]); idx +=1
        points.append( (px, py) )

    def is_on_segment(px, py, x1, y1, x2, y2):
        # Check if (px, py) is on segment (x1,y1)-(x2,y2)
        cross = (x2 - x1)*(py - y1) - (y2 - y1)*(px - x1)
        if cross != 0:
            return False
        # Now check if px is between x1 and x2, and py between y1 and y2
        if min(x1, x2) <= px <= max(x1, x2) and min(y1, y2) <= py <= max(y1, y2):
            return True
        else:
            return False

    for px, py in points:
        on_boundary = False
        crossings = 0
        for x1, y1, x2, y2 in edges:
            # Check if point is on the edge
            if is_on_segment(px, py, x1, y1, x2, y2):
                on_boundary = True
                break
            # Check if the ray crosses the edge
            # We need to check if the edge crosses the horizontal line at py
            # and if the intersection is to the right of px
            # Handle cases where the edge is horizontal
            if y1 == y2:
                continue  # horizontal edge, no crossing
            # Determine if py is between y1 and y2
            if y1 <= py < y2 or y2 <= py < y1:
                # Compute the x coordinate of the intersection
                # Avoid floating point by using fractions
                # But here we use float since n and m are small
                x_intersect = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
                if x_intersect > px:
                    crossings += 1
        if on_boundary:
            print("BOUNDARY")
        else:
            if crossings % 2 == 1:
                print("INSIDE")
            else:
                print("OUTSIDE")

if __name__ == "__main__":
    main()