Solved

How Can I DO That

Posted on 2015-01-09
5
68 Views
Last Modified: 2015-02-06
Consider a two dimensional co-ordinate system with two axes; X & Y. This system is identified by positive integer co-ordinates. Meaning, every valid point in this system is represented by two values (x, y) where 0 < x,y <100.
 
You are given an input set of lines, specified by the co-ordinates of the two end-points.
 
Write a program to identify all closed shapes created by the specified lines.
 
Input Format (the program should accept this simple text file called "input.txt" placed in the classpath):
 
A1, B1; C1, D1
A2, B2; C2, D2

An, Bn; Cn, Dn
 
Expected Output (based on actual values of the input lines):
 
There are two triangles and 1 square based on the input.
Triangle 1  with vertices (a1,b1; a2, b2; a3,b3)
Triangle 2 with vertices (a5,b5; a6, b6; a7, b7)
Square 1 with vertices (a8, b8; a9, b9; a10, b10; a11, b11)
 
Note:
 
The input data may be such that some shapes overlap.
You don't have to find shapes formed by intersection of two shapes. For example, if a square and triangle overlap such that there is another small triangle formed at the intersection, you don't have to report that.
For the sake of scope, report only the following shapes, if any - triangle, any quadrilateral, pentagon. 

Open in new window

0
Comment
Question by:Naren Kumar
5 Comments
 
LVL 24

Expert Comment

by:Phillip Burton
ID: 40539898
Is this a homework task?
0
 
LVL 84

Accepted Solution

by:
ozo earned 250 total points
ID: 40539902
For a brute force approach you could have a table for each of the 10201 possible points listing all the points to which it is connected by a line.

You could then take the triple, quadruple, and pentuple closures of that list.
0
 
LVL 85

Assisted Solution

by:Mike Tomlinson
Mike Tomlinson earned 250 total points
ID: 40540632
You could also do it by building a graph where each node contains the two endpoints and they point to other nodes that have a point in common.  Then traverse the graph and count the number of edges you traveled before coming to a point you've already seen (meaning it is closed).  It simply specifies triangle, quadrilateral and pentagon (not regular pentagon or specific quads like parallelogram, rectangle or square) so you don't need to worry about angles or anything.
0

Featured Post

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Calculate Trendline 4 297
How to build an APP for tablets 1 271
probability of flush draw in texas hold em poker 30 109
Math homework question 5 62
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now