10824  Regular Polygon
Moderator: Board moderators

 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 noone got AC, but after rejudge there are 30something AC's. So, if you got WA during contest, you can check if you got AC and stop looking for nonexistent bugs in your code.
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
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 1e8 accuracy? Do you have other inputs?
Thanx;
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 1e8 accuracy? Do you have other inputs?
Thanx;
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 oneline 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.
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 oneline 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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 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?!

 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..
Check out http://www.algorithmist.com !

 New poster
 Posts: 5
 Joined: Wed Mar 16, 2005 1:40 am
 Location: Brazil
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 kgon 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.
 sorting all points O(n lg n)
 for k from 3 to n,
  for j from 1 to n
   loop to see if a kgon 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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
In checking whether a kgon 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 (k1) * lg(nj) binary search would be faster than that. May be I'll try that later.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 kgon with pt j is possible
Sanny
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
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
I finally got AC for this one.
If anyone needs testcase for this problem, use the following code:
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;
}