Segments
SRM 303 · 2006-05-18 · by Snail
Problem Statement
You are given two line segments on the plane. Each segment is parallel to either the X axis or the Y axis. Your task is to figure out how the segments intersect and return one of the following strings:
- "NO", if the segments do not intersect
- "POINT", if the segments' intersection forms a point
- "SEGMENT", if the segments' intersection forms a line segment
The segments will be given as two int[]s s1 and s2. Each of them will contain four integers x1, y1, x2, y2 (in that order) where (x1, y1), (x2, y2) are segment endpoints.
Constraints
- Each of s1 and s2 will contain exactly four elements
- All integers in s1 and s2 will be between -1000 and 1000, inclusive
- Each segment will be parallel to either the X axis or the Y axis
{0, 0, 0, 1}
{1, 0, 1, 1}
Returns: "NO"
The segments are parallel and there is no intersection.
{0, 0, 0, 1}
{0, 1, 0, 2}
Returns: "POINT"
The segments are located on the same line and have only one common point (0,1).
{0, -1, 0, 1}
{-1, 0, 1, 0}
Returns: "POINT"
The segments intersect at point (0,0).
{0, 0, 2, 0}
{1, 0, 10, 0}
Returns: "SEGMENT"
The segments have a common line segment from (1,0) to (2,0).
{5, 5, 5, 5}
{6, 6, 6, 6}
Returns: "NO"
These are two different points.
{10, 0, -10, 0}
{5, 0, -5, 0}
Returns: "SEGMENT"
The segments have a common line segment from (-5,0) to (5,0).
Submissions are judged against all 69 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Segments with a public method string intersection(vector<int> s1, vector<int> s2) · 69 test cases · 2 s / 256 MB per case