This problem (see below) has been given as a High School Programming League code golf challenge. The shortest codes submitted during the contest were: 177 bytes in Ruby, 212 bytes in Python 2.5, 265 bytes in C. Can anyone make it shorter? Other programming languages are also allowed.

Problem formulation: Given 8 integers: -1000 < x1, y1, x2, y2, x3, y3, x4, y4 < 1000. Check what is the shape of the intersection of two axis-aligned rectangles: P1 = (x1, y1), (x1, y2), (x2, y2), (x2, y1) and P2 = (x3, y3), (x3, y4), (x4, y4), (x4, y3).

* If the rectangles do not intersect print *nothing*.
* If there is exactly one point in common print *point*.
* If the intersections of P1 and P2 is a line segment print *line*.
* If they have a rectangular area in common print *rectangle*. 

Input data specification: The first line contains the number of test cases t (1<=t<1000). Each of the following t lines contains 8 integers: x1, y1, x2, y2, x3, y3, x4, y4 (The area of both rectangles is greater than 0).

You can test your solution here.

  • \$\begingroup\$ How come I don't see any submitted solutions to this problem? \$\endgroup\$ Mar 12, 2011 at 6:29
  • \$\begingroup\$ @Keith Randall The contest session is over, results for submitted solutions are summarized here \$\endgroup\$
    – kuszi
    Mar 12, 2011 at 10:55
  • \$\begingroup\$ What if the coordinates don't make rectangles? What if the shapes overlap to form a shape other than a rectangle? \$\endgroup\$
    – 0WJYxW9FMN
    Jan 2, 2017 at 14:30
  • \$\begingroup\$ @J843136028 you can assume that they do form a rectangle. To the second part off the question I can see now that it is not mentioned that rectangles are axis-aligned (missing word added). \$\endgroup\$
    – kuszi
    Jan 3, 2017 at 14:57

2 Answers 2


Python, 200 characters

f=lambda a,b,c,d:min(2,sum((x-c)*(x-d)<=0for x in range(min(a,b),max(a,b)+1)))
for i in' '*input():z=map(int,raw_input().split());print('nothing','point','line',0,'rectangle')[f(*z[::2])*f(*z[1::2])]

f returns:

0 if the intervals [a,b] and [c,d] don't overlap
1 if the intervals [a,b] and [c,d] overlap in only one point
2 if the intervals [a,b] and [c,d] overlap in a range of points

OCaml, 265 chars

let a,c,p=abs,compare,print_endline
let q s t u v w x y z=match
let()=for n=1 to read_int()do Scanf.scanf"%d %d %d %d %d %d %d %d\n"q done

Uses (abuses) the fact that compare returns 0, 1 or -1. This is not guaranteed according to its documentation but true with OCaml 3.10.1.

  • \$\begingroup\$ Nice! One suggestion:I would write Scanf.scanf" %d %d %d %d %d %d %d %d" (-1 char) \$\endgroup\$
    – kuszi
    Mar 18, 2011 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.