## 10824 - Regular Polygon

Moderator: Board moderators

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

### 10824 - Regular Polygon

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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Excuse me. What's the expected complexity of the algorithm? Is an O(n^2) solution what the judge wants? Thx~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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.

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

ReiVaX18
New poster
Posts: 11
Joined: Mon Mar 29, 2004 11:53 am
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;

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Diego Caminha
New poster
Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil
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?!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Depends on what you mean by "different".. they're the same for some epsilon..

Diego Caminha
New poster
Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil
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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
I get TLE with an n2log(n) solution

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

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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;
}
``````