## Search found 16 matches

Tue Feb 02, 2016 9:15 pm
Forum: Algorithms
Topic: Maximum inscribed circle in any polygon
Replies: 3
Views: 3926

### Re: Maximum inscribed circle in any polygon

Hi VickieMikkelson,

Sounds like you have a clean geometric question. If the drawing in http://jwilson.coe.uga.edu/emt725/Octagon/Octagon.html next to item 8 is what you are looking for, there's an analytical answer: The square peg has to have a side with width w = r*(1+sqrt(2))/sqrt(1+sqrt(0.5))
Sun May 17, 2015 12:32 am
Forum: Algorithms
Topic: Maximum inscribed circle in any polygon
Replies: 3
Views: 3926

### Re: Maximum inscribed circle in any polygon

I saw this really old post - but I like the problem - so I thought about it for while. Here's my a solution. It's a kind of "flooding" algorithm. 1.) Use a rectangular map with the polygon completely inside (not touching the edges) 2.) Initialize each dot of your map with 0 (="not forbidden as cente...
Mon Nov 26, 2007 11:00 pm
Forum: Algorithms
Topic: Challenge in a DP problem
Replies: 3
Views: 2599
Hi fpavetic! It took me a while to understand ... but now I really can see the brilliance in the exponential time algorithm for the subset sum problem (from Horowitz and Sahni). Thanks for that link to wikipedia. My first own idea was to split the set A into two sets (A1 and A2) with A1 holding the ...
Sun Nov 25, 2007 4:20 am
Forum: Algorithms
Topic: Challenge in a DP problem
Replies: 3
Views: 2599
Hey 7erry! I've just came across your posting and although I don't know much about DP I was wondering if you have also thought about a second way of looking at your problem. The eqivalent problem is to pick a subset B out of the set A={x1,x2,...,xn} where the sum of all elements of B is "closest" to...
Sun Nov 25, 2007 3:47 am
Forum: Algorithms
Topic: Bitwise operations
Replies: 2
Views: 2367

### bitwise operations in SUDOKU Solver

I enjoyed using bitwise operations for a (quite fast) sudoku solver. Each field of the sudoku is represented by a bitmask where each bit stands for a possible number (so in standard sudoku you will use 9 bits in each bitmask). If only one bit is set in the bitmask - the only correct number for this ...
Sun Feb 29, 2004 12:11 pm
Forum: Algorithms
Topic: A point on a great circle
Replies: 1
Views: 1054
Hi! Well that formula is not correct - it looks like a linear interpolation - but that does not work on sphere. One counterexample would be: latidude_A = latitude_B = 45 deg ... then latitude_C would also have to 45 deg (for all C-points) - but that is not a great circle. To get the unique great cir...
Sat Dec 13, 2003 3:07 pm
Forum: Volume 1 (100-199)
Topic: 149 - Forests
Replies: 37
Views: 3804

### 149 - Forests

Dear junbin, Here are some more test cases from my AC program. Note that each test case can potentially be used with 8 input variations which can be achieved with the following operations: x <--> (1-x) y <--> (1-y) x <--> y These 8 variations should always deliver the same results. You can check the...
Tue Oct 14, 2003 6:28 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 30447
Hi razibcse!

The only floating point operation I can see at a first glance is the sqrt() function. I assume you passed a "very large" (and therefore overflowed to negative) 'long' argument to sqrt(). Watch out for the range you are using.

Yours, Eric
Tue Aug 26, 2003 11:36 pm
Forum: Off topic (General chit-chat)
Topic: How old are you? Statistics.
Replies: 121
Views: 174173
Hi Folks, I'm 37 ... and I wouldn't have posted my age if "little joey" wouldn't have. I've solved 7 problems since Jan 2003 (and have contributed 1). I would like to express my deep respect towards anybody who has honestly solved hundreds or even beyond 1000! Wow! That is a "level" (rate) way beyon...
Wed Aug 20, 2003 5:18 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 30447
Sorry folks, I have to revise my own posting after a few learning cycles with TLE. I finally got AC (1.664 seconds). Here some new (and better) hints: A.) Forget the algorithm for calculating the digit sum! When going up through the odd numbers (3,5,7, ...) and checking for digit primes you can keep...
Tue Aug 19, 2003 5:50 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 30447
Dear Faizur, A few hints for an efficient solution of Shahriar’s problem „Digit Primes“ (10533). I’ve just started working on the program ... these are the major parts of my „design“: 1.) To count the number of „Digit Primes“ within the range [t1, t2] means to first check if the number is prime and ...
Sun Aug 10, 2003 8:14 am
Forum: Volume 105 (10500-10599)
Topic: 10512 - A Day in Math-land
Replies: 52
Views: 12353

### 10512 - Where's the tricky input?

Dear Shahriar, dear carneiro, First of all I want to congratulate You, Shahriar, on this very interesting problem 10512 (A Day in Math-land) which is exactly my taste. I've got AC (after a few "learning cycles") and I've also chosen the "pure" integer arithmetic solution (using long long and a self ...
Thu Apr 24, 2003 5:33 am
Forum: Algorithms
Topic: Numerical Methods
Replies: 4
Views: 2491
Hi folks, I suppose you mean by "Numerical Methods" that the Computer does not simply perform the calculation of one equation but has to iterate to get a "non-analytical" or "transcendental" solution. If that is what you mean ... then try problem 849 - Radar Tracking . I'm "breeding" over that one r...
Wed Jan 29, 2003 6:09 am
Forum: Volume 1 (100-199)
Topic: 149 - Forests
Replies: 37
Views: 3804
Hi opcode! The on-line judge accepted my new C-code for "forests". My first algorithm was actually correct ... but the optimizing work on it (because of exceeded run-time limit) brought in an error which actually would have been easy to find if I would have used the obvious "extreme" input case: 0.5...
Wed Jan 15, 2003 6:47 am
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3567
Hi all, The 2nd code from prilmeie looks functional now, although it still carries some "unnecessary code": e.g. the expression ( result - a != b || result - b != a ) is never true since + and - are performed in a "circular" manner. You can simply try that out on any debugger. The code from Jordan i...