11186 - Circum Triangle
Moderator: Board moderators
11186 - Circum Triangle
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.
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.
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
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.
There is a solution with O(n) too.
For the previous posted test, my code outputs
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 solutionsrio wrote:There is a solution with O(n) too.
For the previous posted test, my code outputsCode: Select all
21341254742 6326026258 93611494 92130101
i get:
21341254742.435440063476562
6326026258.263971328735352
93611493.600922271609306
92130100.976980358362198
>> DP
I's not so hard. Just evaluate the O(n^3) solution.
>> fpavetic
If you output like below, I think there would be no precision issue with rounding.
I's not so hard. Just evaluate the O(n^3) solution.
>> fpavetic
Code: Select all
21341254742.435253143310547
6326026258.263983726501465
93611493.600922450423241
92130100.976980507373810
Code: Select all
printf("%.0f\n", result);
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.
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;
}
Please help..
Hello. I want to know O(n^2) and O(n) algorithm about this problem.
Would you give me some hint?
Thanks
Would you give me some hint?
Thanks
Oops. How fool I am. I forgot the sortingsErik wrote:Hello,Thanks rio!There is a solution with O(n) too.
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

Sory you guys.
I think we are doing the same solution, Erik.
Need help
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.
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.