11186 - Circum Triangle

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

11186 - Circum Triangle

Post by deepesh » Sun Mar 04, 2007 1:11 pm

I thought a nc3*(16) test cases would not result in TLE. But I could never get it working in the contest.

Is there any trick that I can use to do this problem. Is the expected order n^3 or is there a better solution?

I pre-calculate all the sin(angle). where angle ranges from 0 to 360. Still I am not able to get it working in time.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Sun Mar 04, 2007 1:18 pm

Hi,

my solution runs in O(n^2) without any precomputation.

Cu, Erik :)

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sun Mar 04, 2007 2:11 pm

can somebody please tell me outputs for following test cases

and if it is not a problem, can one tell me his result BEFORE rounding too, i suspect i am having precision issue

http://fpavetic.googlepages.com/11186.big1
http://fpavetic.googlepages.com/11186.big2
http://fpavetic.googlepages.com/11186.big3
http://fpavetic.googlepages.com/11186.big4
Last edited by fpavetic on Thu Mar 08, 2007 12:02 pm, edited 1 time in total.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Mar 04, 2007 3:40 pm

There is a solution with O(n) too.

For the previous posted test, my code outputs

Code: Select all

21341254742
6326026258
93611494
92130101

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Sun Mar 04, 2007 4:45 pm

Hi rio,
Would you kindly give me some hints about O(n)?
Or you can PM me.

thnx

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sun Mar 04, 2007 5:13 pm

rio wrote:There is a solution with O(n) too.

For the previous posted test, my code outputs

Code: Select all

21341254742
6326026258
93611494
92130101
can you please tell me what do you get before you round your solutions

i get:
21341254742.435440063476562
6326026258.263971328735352
93611493.600922271609306
92130100.976980358362198

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Mar 04, 2007 6:04 pm

>> DP
I's not so hard. Just evaluate the O(n^3) solution.

>> fpavetic

Code: Select all

21341254742.435253143310547
6326026258.263983726501465
93611493.600922450423241
92130100.976980507373810
If you output like below, I think there would be no precision issue with rounding.

Code: Select all

printf("%.0f\n", result);

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

Post by deepesh » Sun Mar 04, 2007 6:09 pm

I have got accepted on this problem with an order n^2 algorithm. But I am not able to think of an order n algorithm. It would be great if some one could give a hint.

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sun Mar 04, 2007 6:13 pm

well, i still cant get it accepted so if anybody can check out my code:

Code: Select all

  removed
  silly, yet frustrating mistake
  thank you deepesh and rio
Last edited by fpavetic on Sun Mar 04, 2007 6:26 pm, edited 2 times in total.

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

Post by deepesh » Sun Mar 04, 2007 6:21 pm

if (n<3) you should not just return, but read the corresponding values as well.

2 10
1.00
359.00

You should not miss reading 1.00 and 359.00 even if you do not process them.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Mar 04, 2007 6:22 pm

Silly bug here.

Code: Select all

        if( n < 3 ) {
            puts( "0" ); continue;
        }

        for( int i = 0; i < n; ++i ) {
            double a;
            scanf( "%lf", &a );
            V[i] = a;
        }

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Sun Mar 04, 2007 11:47 pm

Hello,
There is a solution with O(n) too.
Thanks rio!
I found a simple O(n) calculation but it still is O(n*log n) as I have to sort the points by angles.
Did you find a way without sorting?

Cu, Erik :)

rainmaker
New poster
Posts: 2
Joined: Sun Mar 04, 2007 3:57 pm
Location: Seoul, South Korea

Please help..

Post by rainmaker » Mon Mar 05, 2007 2:22 am

Hello. I want to know O(n^2) and O(n) algorithm about this problem.
Would you give me some hint?
Thanks

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Mar 05, 2007 4:09 am

Erik wrote:Hello,
There is a solution with O(n) too.
Thanks rio!
I found a simple O(n) calculation but it still is O(n*log n) as I have to sort the points by angles.
Did you find a way without sorting?

Cu, Erik :)
Oops. How fool I am. I forgot the sortings :oops: My solution is O(n*log n).
Sory you guys.

I think we are doing the same solution, Erik.

rainmaker
New poster
Posts: 2
Joined: Sun Mar 04, 2007 3:57 pm
Location: Seoul, South Korea

Need help

Post by rainmaker » Thu Mar 08, 2007 9:41 am

Hello. I got TLE in last contest. I tried it using O(n^3) algorithm.
I've heard that there are O(n^2) and O(nlogn) algorithm.
I've thought of it since last contest, but I don't know about that.
Would you kindly give me some hints about O(n^2) or O(nlogn)?
Or you can PM me.

Thanks.

Post Reply

Return to “Volume 111 (11100-11199)”