Problem 165

[MrNightLifeLover]

I'm quite desperate with this problem, I think my algorithm is correct (but I could be wrong of course..) I used C++ and boost::rational so there are no problems with floating point precision.. In order to ensure that the code works correct, I wrote a simple visualization which creates matlab code which then displays the line segments and the intersections found. The picture for the first 20 segments is attached. I get 46 intersections, is this correct?

Intersections.jpg

[stijn263]

-> Are you checking wether more than 2 lines intersect at a point ?
-> What about linesegments that are exactly the same (perhaps partly)?

[MrNightLifeLover]

-> Are you checking wether more than 2 lines intersect at a point ?

All the intersection points are stored in a vector. Duplicates are removed after processing all segments. I only get a few duplicates for the intersections of all the 5000 segments.

-> What about linesegments that are exactly the same (perhaps partly)?

My algorithm checks for parallel segements, if two segements are parallel then they do not intersect..

Probably a dumb mistake somewhere.. anybody willing to look at my code? (C++, STL and boost::rational)

[elendiastarman]

My algorithm checks for parallel segements, if two segements are parallel then they do not intersect..

Which is true...unless they're the same line (at least in part). In such cases, there are an infinity of intersection points...

That help?

[stijn263]

In that case, add 0 to the counter instead of infinity

[MrNightLifeLover]

"The first four numbers computed according to the above generator should be: 27, 144, 12 and 232"

If you look at the picture you can see that the numbers are completely wrong (but the intersection algo was not). The problem was a simple integer overflow when generating the "random" numbers. Sorry for the dumb question, I get the correct answer now.

[Raman]

Is the number of intersection points for taking upon within range of
upto first 100 line segments exactly being equal to 1137? rather
within that way

I consistently get up within this same result irrespective of whether
I take up with double, or otherwise numerator/denominator integral
ratio for upon the variables, ...

For upto 5000 line segments, I consistently get upon with either
xx, or otherwise xx though! (results skipped by hk)

For being upto wrong solution upon this problem, that case is being up
To be clear enough, thus man

Raman.png

[hk]

For 100 I get 1112.
As you are not supposed to post code fragments or results I'm going to delete your results for 5000 segments.

[Raman]

Can someone please confirm about this following fact

The number of intersection points for which values for x-coordinates of intersection points
is being less than 10, is exactly equal being to 543?

to be clear, cleanly enough
exactly itself rather within that way
properly -y- y - ry ly -y y ()y ()-y (-)y y n m - l r - () ()- (-) - - - - - - - - - - -
- -

Edit: Never mind, that I had solved up within this problem
No problems at all, first of all within any such case
thus being all at once, for this case man

ok alright then

206/344
as such for
18.8.2011
all at once

[Yaptro]

Oh, I all time get 2869010. Maybe it's because I didn't delete repeats?...

[mdean]

Well, this problem is causing way more headaches than expected. For some reason, I'm getting 1300 intersections for the first 100 segments. Apparently not a good sign.

So far, I've avoided putting fractions in this and I don't think that's going to make the difference in right or wrong at the moment. Since I'm apparently too high, I'll probably start by checking some of the points of intersection and see if they're correct.

Update: Ugh! After updating with a fraction class, I realize the problem is I started with $t_0$ instead of $t_1$...

[oleglyamin]

Could someone verify the following?

For N = 500 segments the answer is 29496.
For N = 700 segments the answer is 57909.

Thanks.

[jake223]

I'm getting the same values as oleglyamin, but the wrong answer on 5000. I believe I've accounted for all the issues stijn mentioned above, and I get the right answer for 100. Would anyone be willing to look at my code (python)?


[20 minutes later] Never mind - I realized I was only doing integer arithmetic most of the time and was using floating-point in a very small case. Working now, and FWIW I still get the same 500 and 700 answers.

[Oliver1978]

From the description I gather that line segments created with that BBS thing are immutable? E. g. t[0;1]-t[2;3], t[4;5]-t[6;7] etc.
Or is it that only two consecutive numbers out of t[] make a point which is then combined with another point to give a line? What I'm talking about is, can a line be made from coordinates e.g. t[0;1]-t[6;7]?

[hk]

From the problem description:

To create each line segment, we use four consecutive numbers t_n.

[Oliver1978]

Thanks for clearing this hk!

IMHO I've built a "fool-proof" algorithm, although we all know: Build a system that also a fool can use, and only fools will use it. Anyway... I'm in the process of eliminating flaws in my algorithm, going from top to bottom. Could anyone confirm
Points[0..4] = [(27, 144), (12, 232), (46, 53), (117, 462), (246, 70)],
Points[123..127] = [(75, 22), (349, 420), (189, 463), (418, 474), (137, 245)],
Points[9999] = (250, 489)?

Additionally, like always, is double precision enough for this problem? I've tried the first two segments (points 0-1 <-> 2-3) and found that they do intersect. I've double-checked the results at arndt-bruenner.de and I've noticed there's already a deviation at 1/100

[TripleM]

Additionally, like always, is double precision enough for this problem?

Without talking specifically about this problem - if you find yourself asking that question, the answer will virtually always be no.

[CherylLynn]

NOTE: I copied my post on the problem thread and hashed out the actual numbers….
I need someone to set me straight. I've had the solution implemented for some time representing all numbers in rational form with the numerator and denominator as __int64's. At 1st I made the mistake of not eliminating duplicate points and had the answer at #####. Once I realized the question stated DISTINCT points, I removed any point that appeared more than once. I found ##### of these points and provided an answer of #####. Still wrong. I hunted and searched for the issue.
Just for grins, I counted any set of duplicates as "1";
This is what I was doing: If a point(x,y) was in the original set more than once I was removing ALL of the instances of (x,y) from the set.
This is what I tried: If a point(x,y) was in the original set more than once I was removing ALL but 1 instance of (x,y) from the set. Now my answer of ##### is correct. Do I have 2 bugs canceling out, or do I have a misunderstanding of what "distinct" means? Did all others leave the 1st instance of (x,y) in the set once a duplicate of it was found?

[traxex]

The following list contains 3 distinct elements: {2, 2, 2, 2, 5, 10, 10, 10}. This is the meaning of "distinct" in this problem and some others. Your interpretation never occurred to me.

[Animus]

Hi, CherylLynn

As pointed out by traxex, it seems that you have mixed up the meaning of "distinct" intersection points with "unique" points. If you were loocking for unique points your first interpretation would have been right to completely exclude points with multiple intersections, for distinct points you have to count all different intersections found, but only once.
This also applies to all other problems in which we ask for distinct entities.