839. Segments intersection

 

Given two line segments on a plane with integer coordinates of their endpoints in the Cartesian coordinate system. Determine whether the segments have at least one common point.

 

Input. The first line contains the coordinates of the first endpoint of the first segment, and the second line contains the coordinates of the second endpoint of the first segment. The third and fourth lines contain the coordinates of the endpoints of the second segment. All coordinates are integers with absolute values not exceeding 104.

 

Output. Print “Yes” if the segments have a common point, and “No” otherwise.

 

Sample input 1

Sample output 1

0 0

1 0

1 0

1 1

Yes

 

 

Sample input 2

Sample output 2

0 0

1 0

2 0

3 0

No

 

 

SOLUTION

geometry

 

Algorithm analysis

The bounding rectangle of a geometric figure is the smallest rectangle with sides parallel to the coordinate axes that completely contains the given figure.

In simpler terms, if we want to “fit” the figure into a rectangle so that all its points lie inside it, the bounding rectangle will have the minimum possible size.

 

Consider a segment with endpoints at (x1, y1) and (x2, y2). To find its bounding rectangle:

·        Determine the lower-left corner of the rectangle:

x1’ = min(x1, x2), y1’ = min(y1, y2)

·        Determine the upper-right corner of the rectangle:

x2’ = max(x1, x2), y2’ = max(y1, y2)

 

Thus, the bounding rectangle is the rectangle with corners (x1’, y1’) and (x2’, y2’) that contains our segment.

 

Lemma. Suppose two segments (x1, x2) and (x3, x4) are given on a line, where x1 < x2 and x3 < x4. The segments do not intersect if and only if either the first segment lies entirely to the left of the second, or the second lies entirely to the left of the first.

 

 

Lemma. Suppose two rectangles (x1, y1) – (x2, y2) and (x3, y3) – (x4, y4) are given in the plane, where x1 < x2, y1 < y2 and x3 < x4, y3 < y4. The rectangles do not intersect if and only if either the segments (x1, x2) and (x3, x4) do not intersect, or the segments (y1, y2) and (y3, y4) do not intersect.

 

Intersection criterion for two segments

Two segments AB and CD intersect if and only if the following three conditions hold:

1.     Their bounding rectangles intersect.

2.     Points C and D lie on different sides of the line AB, or at least one of the points C or D lies on the line AB. This means that

[AB ? AC] * [AB ? AD] ? 0

3.     Points A and B lie on different sides of the line CD, or at least one of the points A or B lies on the line CD. This means that

[CD ? CA] * [CD ? CB] ? 0

 

Below are various cases of the relative positions of two segments and the corresponding values of the cross products.

 

In the next example, each segment intersects the line containing the other segment. However, their bounding rectangles do not intersect.

Example

In the first example, the segments intersect. In the second example, they do not.

 

Algorithm implementation

Since the coordinates of the segment endpoints are integers, we’ll use only the integer type long long for calculations. Later, we’ll need a function sgn that determines the sign of a number n.

 

int sgn(long long n)

{

  return (n > 0) - (n < 0);

}

 

The function RectanglesIntersects takes as arguments the coordinates of the bounding rectangles for segments AB and CD. It returns 1, if the rectangles (x1, y1) – (x2, y2) and (x3, y3) – (x4, y4) intersect, and 0 otherwise.

 

int RectanglesIntersect(long long x1, long long y1,

                        long long x2, long long y2,

                        long long x3, long long y3,

                        long long x4, long long y4)

{

 

  if (x2 < x3 || x4 < x1) return 0;

  if (y2 < y3 || y4 < y1) return 0;

  return 1;

}

 

The function cross computes the cross product of two vectors (Ax, Ay) and (Bx, By).

 

long long cross(long long Ax, long long Ay,

                long long Bx, long long By)

{

  return Ax * By - Ay * Bx;

}

 

The function intersect checks whether the segments AB and CD intersect.

 

int segmentsIntersect(long long x1, long long y1,

                      long long x2, long long y2,

                      long long x3, long long y3,

                      long long x4, long long y4)

{

 

Check the intersection of the bounding rectangles. If they do not intersect, return 0.

 

  if (!RectanglesIntersect(

       min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2),

       min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4))

     ) return 0;

 

Construct the vectors AB, AC, AD.

 

  long long ABx = x2 - x1, ABy = y2 - y1;

  long long ACx = x3 - x1, ACy = y3 - y1;

  long long ADx = x4 - x1, ADy = y4 - y1;

 

Construct the vectors CD, CA, CB.

 

  long long CDx = x4 - x3, CDy = y4 - y3;

  long long CAx = x1 - x3, CAy = y1 - y3;

  long long CBx = x2 - x3, CBy = y2 - y3;

 

Compute the cross products.

 

  long long ABxAC = cross(ABx, ABy, ACx, ACy); // AB x AC

  long long ABxAD = cross(ABx, ABy, ADx, ADy); // AB x AD

  long long CDxCA = cross(CDx, CDy, CAx, CAy); // CD x CA

  long long CDxCB = cross(CDx, CDy, CBx, CBy); // CD x CB

 

Check points 2 and 3 of the segment intersection criterion. If they are not satisfied, return 0. To avoid overflow, the comparison with zero should be done not on the product of the numbers themselves, but on the product of their signs.

 

  if (sgn(ABxAC) * sgn(ABxAD) > 0) return 0;

  if (sgn(CDxCA) * sgn(CDxCB) > 0) return 0;

  return 1; // Segments intersect

}

 

The main part of the program. Read the input data.

 

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);

scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);

 

Check the intersection of the segments.

 

if (segmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4))

  puts("Yes");

else

  puts("No");