Counting Rectangles

Computer Science Level 4

Among all quadrilaterals , Chris likes rectangles the most, especially the ones which have their sides parallel to the axes. This file contains information of 1000 quadrilaterals. How many of them are rectangles that meet this criteria?

Input Format

Each quadrilateral is described in two lines. The first line contains 4 integers $x_1, x_2,x_3, x_4$ and the second line contains 4 integers $y_1,y_2,y_3,y_4$ . This indicates a quadrilateral with vertex $(x_1,y_1), (x_2,y_2), (x_3,y_3), (x_4,y_4)$ (not necessary in clockwise / anticlockwise order).

Details and Assumptions :

It is guaranteed that for a quadrilateral no points will be in the same spot.
$1\leq (x_i,y_i) \leq 100$

The answer is 590.

2 solutions

Agnishom Chattopadhyay
Jul 14, 2016

The key to avoid the tedious work is to sort the points first by the x-coordinates, and then by the y-coordinates. In python, the sorted function does that automatically for 2-tuples.

Here is my solution:

def isRect(points):
    points.sort()
    bottomleft = points[0]
    topright = points[3]
    if bottomleft[0] == points[1][0] and bottomleft[1] == points[2][1] and \
    topright[0] == points[2][0] and topright[1] == points[1][1]:
            return True
    return False

import urllib2
source = urllib2.urlopen("http://pastebin.com/raw/21v3jtXU")
counter = 0
for iii in xrange(1000):
    xdata = map(int, source.readline().split())
    ydata = map(int, source.readline().split())
    points = zip(xdata, ydata)
    if isRect(points):
            counter += 1

print counter

That prints 590

Hm, are you assuming that the rectangle must have sides parallel to the axis? IE $(1,0), (0,1), (-1, 0), (0,-1)$ also forms a rectangle.

So it would be better to replace with a more general rectangle equation.

Calvin Lin Staff - 4 years, 11 months ago

You are right. I hadn't considered that. Strangely, the test case contained no such rectangle.

Agnishom Chattopadhyay - 4 years, 11 months ago

@Christopher Boo You should have a question where the cases involve a tilted rectangle :)

Calvin Lin Staff - 4 years, 11 months ago

@Calvin Lin – Actually for this problem I want to show a neat trick (that only works on non-tilted rectangle) to verify if the four points form a rectangle. I have added the solution. For the non-tilted one, the only solution I have in mind now is heavy case check. I'll post one once I figured out an elegant solution.

Christopher Boo - 4 years, 10 months ago

Christopher Boo
Jul 23, 2016

Noticed that if the four points form a rectangle that is parallel to the axes, there will be 2 pairs of $x$ with the same value, same goes for $y$ . For example, $(0,0), (0,1), (1,0), (1,1)$ , $x$ has 2 $0$ 's and 2 $1$ 's, $y$ has 2 $0$ 's and 2 $1$ 's. Since it is guaranteed that no points will be in the same spot, the inverse is also true. To check if the 4 numbers form 2 pairs, simply XOR the 4 value and they should equal to $0$ since $a\oplus a = 0$ .

1
2
3

def check_rect(x1,y1,x2,y2,x3,y3,x4,y4):
    if x1 ^ x2 ^ x3 ^ x4 == 0 and y1 ^ y2 ^ y3 ^ y4 == 0:
        return True

Counting Rectangles

The answer is 590.

2 solutions

0 pending reports