10824 - Regular Polygon

stubbscroll · Post by **stubbscroll** » Wed Mar 09, 2005 4:31 pm

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 · Post by **Observer** » Wed Mar 09, 2005 5:10 pm

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

stubbscroll · Post by **stubbscroll** » Wed Mar 09, 2005 5:14 pm

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.

ReiVaX18 · Post by **ReiVaX18** » Wed Mar 09, 2005 10:01 pm

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 · Post by **Observer** » Thu Mar 10, 2005 12:39 pm

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.

Diego Caminha · Post by **Diego Caminha** » Wed Mar 16, 2005 1:58 am

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 · Post by **Larry** » Wed Mar 16, 2005 3:37 am

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

Diego Caminha · Post by **Diego Caminha** » Wed Mar 16, 2005 6:22 am

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 · Post by mf » Wed Mar 16, 2005 1:05 pm

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 · Post by **Sanny** » Sat Apr 09, 2005 8:59 pm

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 · Post by **Observer** » Tue Apr 12, 2005 10:50 am

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.

Sanny · Post by **Sanny** » Wed Apr 13, 2005 4:07 pm

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 · Post by **Emilio** » Fri Apr 14, 2006 5:41 pm

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

Hadi · Post by **Hadi** » Mon Aug 14, 2006 6:54 am

I get TLE with an n2log(n) solution

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

Hadi · Post by **Hadi** » Mon Aug 14, 2006 8:18 am

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;
}