8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How come I don't see any submitted solutions to this problem? \$\endgroup\$ – Keith Randall Mar 12 '11 at 6:29
  • \$\begingroup\$ @Keith Randall The contest session is over, results for submitted solutions are summarized here \$\endgroup\$ – kuszi Mar 12 '11 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 '17 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 '17 at 14:57
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

OCaml, 265 chars

let a,c,p=abs,compare,print_endline
let q s t u v w x y z=match
c(a(s-u)+a(w-y))(a(s+u-w-y)),
c(a(t-v)+a(x-z))(a(t+v-x-z))with
0,0->p"point"|0,1|1,0->p"line"|1,1->p"rectangle"|_->p"nothing"
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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