Search found 16 matches

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

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))
by ericschmidt
Sun May 17, 2015 12:32 am
Forum: Algorithms
Topic: Maximum inscribed circle in any polygon
Replies: 3
Views: 4048

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...
by ericschmidt
Mon Nov 26, 2007 11:00 pm
Forum: Algorithms
Topic: Challenge in a DP problem
Replies: 3
Views: 2657

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 ...
by ericschmidt
Sun Nov 25, 2007 4:20 am
Forum: Algorithms
Topic: Challenge in a DP problem
Replies: 3
Views: 2657

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...
by ericschmidt
Sun Nov 25, 2007 3:47 am
Forum: Algorithms
Topic: Bitwise operations
Replies: 2
Views: 2425

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 ...
by ericschmidt
Sun Feb 29, 2004 12:11 pm
Forum: Algorithms
Topic: A point on a great circle
Replies: 1
Views: 1086

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...
by ericschmidt
Sat Dec 13, 2003 3:07 pm
Forum: Volume 1 (100-199)
Topic: 149 - Forests
Replies: 37
Views: 4435

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...
by ericschmidt
Tue Oct 14, 2003 6:28 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 31720

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
by ericschmidt
Tue Aug 26, 2003 11:36 pm
Forum: Off topic (General chit-chat)
Topic: How old are you? Statistics.
Replies: 121
Views: 175569

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...
by ericschmidt
Wed Aug 20, 2003 5:18 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 31720

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...
by ericschmidt
Tue Aug 19, 2003 5:50 am
Forum: Volume 105 (10500-10599)
Topic: 10533 - Digit Primes
Replies: 108
Views: 31720

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 ...
by ericschmidt
Sun Aug 10, 2003 8:14 am
Forum: Volume 105 (10500-10599)
Topic: 10512 - A Day in Math-land
Replies: 52
Views: 12888

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 ...
by ericschmidt
Thu Apr 24, 2003 5:33 am
Forum: Algorithms
Topic: Numerical Methods
Replies: 4
Views: 2558

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...
by ericschmidt
Wed Jan 29, 2003 6:09 am
Forum: Volume 1 (100-199)
Topic: 149 - Forests
Replies: 37
Views: 4435

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...
by ericschmidt
Wed Jan 15, 2003 6:47 am
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3647

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...

Go to advanced search