Page **1** of **2**

### 10824 - Regular Polygon

Posted: **Wed Mar 09, 2005 4:31 pm**

by **stubbscroll**

In case some people didn't notice it, this problem seems to have been rejudged and the contest ranklist is changed. I just checked the ranklist and noticed it was different. During the contest no-one got AC, but after rejudge there are 30-something AC's. So, if you got WA during contest, you can check if you got AC and stop looking for non-existent bugs in your code.

Posted: **Wed Mar 09, 2005 5:10 pm**

by **Observer**

Excuse me. What's the expected complexity of the algorithm? Is an O(n^2) solution what the judge wants? Thx~

Posted: **Wed Mar 09, 2005 5:14 pm**

by **stubbscroll**

Observer wrote:Excuse me. What's the expected complexity of the algorithm? Is an O(n^2) solution what the judge wants? Thx~

My solution is O(n^2) with some optimizations, and runs in 0.2 seconds.

[edit] Sorry, but my solution is actually O(n^3), still with optimizations.

Posted: **Wed Mar 09, 2005 10:01 pm**

by **ReiVaX18**

Hi!

I am trying to solve this problem but only obtain WA. I sorted the points by their angle and searched the candidates to form the polygon using lower_bound(). I think this should be correct but I always get WA.

I generated an input with points of the form (cos(2*PI/2000.0), sin(2*PI/2000.0)) and get the correct result (4 500, 5 400, 8 250, etc.) and tried other inputs. Is there a problem with the 1e-8 accuracy? Do you have other inputs?

Thanx;

Posted: **Thu Mar 10, 2005 12:39 pm**

by **Observer**

I also get so many WA...... Please could anybody post some test data here?

Btw, what's the time limit for this task during contest? 2 seconds?

- EDIT -

Just got AC with an O(n^2) algorithm, without much optimization. That runs for ~3 sec, and I guess that's quite slow...... Will try to improve it after dinner~~

- EDIT (2nd) -

With a one-line pruning statement I get down to 1.8 seconds. Probably won't put any more effort on improving that. May try O(n^3) instead.

Posted: **Wed Mar 16, 2005 1:58 am**

by **Diego Caminha**

Maybe there's a problem in the judge data. After many WA I got accepted just chaging the way a calculated the radius. Instead of using the first x and y, I used the last ones. I did that after I found out that my program calculated differents radius by the simple formula "radius = sqrt(x^2 + y^2)". But shouldn't all them be the same size since they are in the same circle?!

Posted: **Wed Mar 16, 2005 3:37 am**

by **Larry**

Depends on what you mean by "different".. they're the same for some epsilon..

Posted: **Wed Mar 16, 2005 6:22 am**

by **Diego Caminha**

By different I mean: fabs(r1-r2) > 1e-8. Maybe epsilon could be larger, but that was the only value I tested. And it was enough to make my solution wrong!

But if it isn't a problem in the judge data, then get it as a warning to the ones who are getting WA.

Posted: **Wed Mar 16, 2005 1:05 pm**

by **mf**

You can avoid computing radii at all - there's function atan2, which gives angle by point's coordinates - exactly what your solution might need. And the standards require it to be as accurate as possible.

Posted: **Sat Apr 09, 2005 8:59 pm**

by **Sanny**

Can anybody explain what is the O(n^2) or O(n^3) algorithm for this problem. I've used an O(n^3 lg n) algrotithm and got AC in ~.2 s and currently 5th in the ranklist. Thanks in advance.

Sanny

Posted: **Tue Apr 12, 2005 10:50 am**

by **Observer**

The O(n^3) solution is just like this:

- sorting all points O(n lg n)

- for k from 3 to n,

- - for j from 1 to n

- - - loop to see if a k-gon with pt j is possible

The O(n^2) one is just a modification of that, with a table. This solution is good in the sense that you don't need any optimization to get it within time limit.

With the online judge, it's not uncommon that O(n^3) codes outrun O(n^2) ones. For instance, in

**Q10667 Largest Block**, my O(n^3) solution managed to get 0.00.006s, faster than most O(n^2) submissions.

Posted: **Wed Apr 13, 2005 4:07 pm**

by **Sanny**

The O(n^3) solution is just like this:

- sorting all points O(n lg n)

- for k from 3 to n,

- - for j from 1 to n

- - - loop to see if a k-gon with pt j is possible

In checking whether a k-gon with pt j is possible, you have to check n -j points, isn't it? I'm not sure but I have a feeling that my (k-1) * lg(n-j) binary search would be faster than that. May be I'll try that later.

Sanny

Posted: **Fri Apr 14, 2006 5:41 pm**

by **Emilio**

Hello all!

I'm trying this problem and always get WA

, I think that a precision problem, I hate it.

But by other hand, my time is 6.000+ secs, and my algorithm is O(n^2), and I have seen that many people have a time less 1 sec.

Could anyone explain his/her algorithm or give me a good hint to reduce this time?

Some test cases will be appreciated too

Posted: **Mon Aug 14, 2006 6:54 am**

by **Hadi**

I get TLE with an n2log(n) solution

Edit: Now, getting WA with an O(n2) solution

Posted: **Mon Aug 14, 2006 8:18 am**

by **Hadi**

I finally got AC for this one.

If anyone needs testcase for this problem, use the following code:

Code: Select all

```
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
ofstream fout("10824.in");
for(int n = 14; n < 30; n++)
{
fout << n << endl;
for(int i = 0; i < n; i++)
{
double b = i * 2.0 * acos(-1.0) / n;
cout << b << endl;
fout.precision(10);
fout.setf(ios::fixed);
fout << cos(b) << " " << sin(b) << endl;
}
}
fout << 0 << endl;
return 0;
}
```