No this will not be used in a project or for any purpose other than this contest, I just wanted it that way to facilitate timing the execution. I also need to check the results to make sure none of your lines cross one another, much easier if the data in in an array which I can then pass to a verification function.Originally Posted by brewbuck
Last edited by abachler; 04-04-2008 at 10:08 AM.
Don't assume that, even if the provided sample did fit into that domain. I just copied and pasted a big array of doubles. I added a 0.0 to the end.I agree.
As for the machine, how many CPUs does it have?
Is the domain and range restricted from -1.0 to 1.0?
The machine I will probably run it on has a single P4 with hyperthreading.
This polygon looks ugly but I think I solved it.
I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.
"The Internet treats censorship as damage and routes around it." - John Gilmore
"I see what you did there..."This polygon looks ugly but I think I solved it.
I will post code later, it's kinda ugly. If you'd zoom this thing in enough, it would look like a nice polygon.
After seeing that it hardly looks like a challenge anymore. Unless abachler changes the rules to disallow this sort of solution.
That solution is perfectly valid. I took a different route, but that one works just as well.
Since there is a valid solution now, Ill go ahead and explain the method I used.
1. Find the geometric center of all the points. This is the origin.
2. Start at theta 0.0 and go clockwise (or CCW). The first point you find is the start of the polygon, now contuinue to increment theta and add each point to the polygon until you get back to the first point.
Last edited by abachler; 04-04-2008 at 11:02 AM. Reason: typso
Well the code has very confusing variable names, that's usually something I never think about when coding. My code is not usually readable to other people.
That happens when I try to code quickly.
Attention! Only look at the code if you want to get a headache!
"The Internet treats censorship as damage and routes around it." - John Gilmore
Could you post a screenshot what your solution looks like?
"The Internet treats censorship as damage and routes around it." - John Gilmore
Sure, soon as I write it, we just worked out the algorithm so far, I'll implement it tonight though. I'd post a pic of the whiteboard solution, but theres other stuff on it atm too. Let me ge that stuff written down adn cleared off then Ill post it.
Last edited by abachler; 04-04-2008 at 02:32 PM.
My dots are the same as yours, our coordinates systems were just different. I flipped mine around and drew a couple lines (manually) to show the image.
Good idea to just progress through the values from one end of the range to the other.
Mainframe assembler programmer by trade. C coder when I can.
How about a twist on this competition?
You have to draw a circle using the points. Who ever draws the shape closest to a circle wins (efficiency taken into consideration also).
It would work something like:
1) Find the area with the highest density of dots.
2) Make a dummy circle there.
3) Find points that are close enough to the circle.
4) Put those dots in the right order.
5) Connect them.
I may be too lazy to try this though.
"The Internet treats censorship as damage and routes around it." - John Gilmore
Sorry, had to work on something else this weekend. I will post the code a soon as I get it finished.
My solution might be what abachler was suggesting, not sure.
long time; /* know C? */
Unprecedented performance: Nothing ever ran this slow before.
Any sufficiently advanced bug is indistinguishable from a feature.
Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
The best way to accelerate an IBM is at 9.8 m/s/s.
recursion (re - cur' - zhun) n. 1. (see recursion)
This looks pretty trivial.
You may have to define M_PI yourself - I always forget if it's predefined.Code:#include <cstddef> #include <cmath> #include <algorithm> const std::size_t NUM_POINTS = (sizeof(xy) / sizeof(xy[0]) - 1) / 2; struct point_with_theta { double x, y, theta; void set(double ax, double ay) { x = ax; y = ay; theta = (x == 0 && y == 0) ? M_PI : std::atan2(y, x); } bool operator <(const point_with_theta &o) const { return theta < o.theta; } }; point_with_theta points[NUM_POINTS]; int main() { for(std::size_t i = 0; i < NUM_POINTS; ++i) { points[i].set(xy[i*2], xy[i*2+1]); } std::sort(points, points+NUM_POINTS); // Points are now in the correct order. Feel free to split them into two arrays or plot them. }
May not be the fastest solution, but it's probably one of the shortest. Complexity is O(N*log(N)). Cache coherency during sorting depends on the std::sort implementation, but should generally be quite nice, since quicksort is pretty good at that stuff. Cache coherency during the copying should be excellent, unless atan2 needs all the cache for itself.
It may be possible to speed up the copying with some SIMD, but copying the values out is tricky with the interleaved format, so it may not be worth it. (Also, the three doubles are inappropriately aligned for SIMD.) In addition, the x87 FPU directly supports atan, while the SSE engine doesn't. An interesting variation would be to split the three components into separate arrays, but this requires you to write your own sort algorithm or a writable zip_iterator (Boost's zip_iterator isn't writable). If you have the parallel arrays, you can SIMD-walk over them to calculate theta, assuming you can write a proper atan2 with SIMD instructions. The case distinction necessary may make this difficult.
If you use the FPATAN x87 instruction, you can omit the zero-check, as the result of that operation is defined for all-zero arguments.
Last edited by CornedBee; 04-14-2008 at 04:49 AM.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
That looks a lot like the results we got on the whiteboard.
