tricky problem

devit · 02-18-2004, 03:27 PM

I have found a nice problem but I couldn't give an appropriate answer to it:
I read from a file n straight lines from their equations (Ax+By+C=0 so I read A, B and C). I have to tell how many polygons the lines determine(only the polygons that can't be broken up will be counted).
for example the equations of four straight lines:
x=0
y=0
x+y-1=0
x-y=0

The answer is 2 but how can I get there in less than a second(surely not backtracking)?

Thanks!

Hko · 02-18-2004, 06:39 PM

Homework from school/university?

jtshaw · 02-18-2004, 07:37 PM

Can you solve it mathematically? Once you can do that this problem is very easy. But I suggest you take a few examples, plot them on a piece of paper, and look at the trends.... I remember grading that one as a TA

Squall · 02-18-2004, 09:21 PM

I'm a little confused, I'm not sure what you are trying to solve for? Are you trying to find the roots of the quadratic? I may be able to find a solution if you tell me what I'm trying to solve.

edit: sorry nevermind, I read the post more thorougly and you did indeed address what you are trying to find.

Squall · 02-18-2004, 09:30 PM

What I'd do with what you have is simply graph the points. The number of polygons the lines make when they intercept it should be the answer. And no, you probably won't ever be able to get there in a second. Some math problem require a bit more.

Let's see if it works

x=0
y=0
x+y-1=0 (y=-x+1)
y=x

hold on a minute...

Yep, we got ourselves two polygons.

NOTE: I'm only in 10th grade, so don't assume I'm right without asking your professor or someone, that's just how I'd do it.

Thanks for the problem, I was bored.