Counting More Rectangles

Computer Science Level 4

Among all quadrilaterals , Chris likes rectangles the most. This file contains information of 10000 quadrilaterals. How many of them are, possibly tilted , rectangles?

Input Format

Each quadrilateral is described in four lines. Each line contains a pair of integers that describes a point ( x , y ) (x,y) . Note that the points are not necessarily in clockwise / anticlockwise order.

Details and Assumptions :

  • It is guaranteed that for a quadrilateral no points will be in the same spot.
  • 1 ≤ ( x i , y i ) ≤ 4 1\leq (x_i,y_i) \leq 4

This is an extension of this problem.


The answer is 103.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Christopher Boo
Jul 23, 2016

We sort the 4 points according to its x x -axis. Then, we check the diagonals, width and height. 

1
2
3
4
5
6
7
8
 
def dist(p,q):
    return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])

def check_rect(points):
    points.sort()
    return dist(points[0],points[3]) == dist(points[1],points[2]) and 
           dist(points[0],points[1]) == dist(points[2],points[3]) and 
           dist(points[0],points[2]) == dist(points[1],points[3])

2 Helpful 0 Interesting 0 Brilliant 0 Confused

This is actually a pretty good solution. I originally thought of trying to sort them in clockwise/anticlockwise order and check for angles, but this works simpler.

Agnishom Chattopadhyay - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...