11114  Polygon Encoder
Moderator: Board moderators
11114  Polygon Encoder
I don't see any indication of the size of the input, but after some testing, the length of the input number should be at most 400 decimal digits.

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
The problem is all about writing the decode function.. the rest is straight forward. I'm getting TLE... Here's my decode function, which decodes a value 'p' into the corresponding row and column 'r' and 'c':
is there a faster method using bigints ???? I deduced a formula for direct calculation of the row and the column (the commented line 'd = ...') instead of binary search, but it involves calculating sqrt, so I couldn't use it with bigint.
any ideas or hints ??
Code: Select all
void decode(type p, type& r, type& c)
{
type l = 0;
type h = p + 1;
while(1 < h  l)
{
type m = (l + h)/2;
if (p < m*(m+1)/2) h = m;
else l = m;
}
//d = (sqrt(1 + 8*p)  1)/2;
type& d = l; // The diagonal number
c = p  (d*d + d)/2;
r = d  c;
}
any ideas or hints ??
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 New poster
 Posts: 33
 Joined: Fri Jan 06, 2006 5:51 pm
Try the cases...
Input:
Output:
Hope these help.
Input:
Code: Select all
211709921225737426682900
348983400808580771
2946876997361
*
Code: Select all
16.0
50.0
3.5
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 11114  Polygon Encoder
The problem should have stated that the points calculated after decoding were already sorted in ccw/cw order.
I had trouble sorting them so that my area calculation would work. (Too many WAs)
I had trouble sorting them so that my area calculation would work. (Too many WAs)
re:
+1

 New poster
 Posts: 1
 Joined: Thu Jun 30, 2011 9:18 pm
 Location: Deutch
 Contact:
ok
ok