But O(N^2 * logN) is death for python

Edited by author 23.08.2024 14:56

rt

Problem statement was updated:
• "All the pieces have distinct coordinates and lie on a table"
• "Coordinates should be precise up to 7 digits"

New tests have been added.
Timelimit was decreased to 3 seconds.
Submissions made after contest have been rejudged.
This problem suppose O(N^2) solution now.

How many digits after the decimal point should we output?

What is it?

My algorithm is to consider every cake A from big to small to check whether Vovan can get. If Vovan wants to get cake A rather than B, he position must be in a certain arc in the cirlce, and the common part of these arcs is the available position. If the common part exists, then there is a solution that Vovan can get cake A.
I've checked my program for many times, but I don't know why I get Wrong Answer at #28. Please help me~

Edited by author 15.03.2007 11:59

I think the tests for this problem are very simple!!!
Here is the solution, which gets AC: I just divide the [-R; R] into 10 (!!!! only 10 !!!!!) parts and for every X from those 10 (!!!) values I calculate two corresponding Y => I get 20 points => calculate the nearest piece for every point and output the one with the biggest piece.

Isn't it to simple???

Interesting why this code gets Crash(2) if it is said that k <= 1000 ????

#include <stdio.h>
int main()
{
int k, r;
scanf("%d%d", &r, &k);
if(k > 1000)
throw 0;
else
printf("6 8\n");
return 0;
}

I saw in the best solutions that there were some programs worked longer than 0.25s . Why could they get AC ?