OJ Board

In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6. The thing is that this is the smallest epsilon I can use without timeouting, I wonder if people that solved it using the nested ternary search approach did something better in complexity than...

Ivan wrote:In the contest it took a few submissions to figure out the right balance between precision and runtime but finally I got "solved".

I've implemented this approach using epsilon=0.0009 but got WA, can you tell me the largest value of epsilon you used to get it solved?

Got AC using your random approach (I had a bug in intializing an array :oops: ). Btw, that "if both sets same size, break" part is wrong, should be "if both sets are of size n, break". Just check that you really break. Funny thing I got AC using my wrong condition, I think there wasn't a testcase fo...

Well I've tried the random approach as follows: while(true){ -randomly generate A, B. That is O(1) -divide the points in two sets where each set lies in one side of the line Ax+BY=0. That is O(n) -if both sets has the same size break } However the soltion also times out! do you make any further enha...

do you mean you randomly choose A then randomly choose B and check if the same number of points lie on each of the line sides?

I think this problem has some mathematical approach (looking at the very small times it has been solved in), any ideas?

I'm trying to solve this problem http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3562 which is very much related to this thread but always get WA actually i'm using Igor's code for mincost max flow, and for max cost I let cost [j] = MaxCost we got-cost [j] and rerun the mincost max...

Can anyone explain how to solve this problem?

Thanks alot

Usually i don't include <cstring>, memset doesn't need it on VC++ and GCC if i remember correctly, but the wierd thing is that i tried to submit the problem now with memset and without including any additional headers and got AC! anyway i'll try cstring the next time i got compilation error for mems...

I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons. I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...) Also can anyone expalin other approaches to ...

Here is my code, #include<algorithm> #include<iostream> using namespace std; #define big int int cNum[4]; big table[5][8][8][8][8][8][5][8]; big get(int firstColor, int firstSize, int c1, int c2, int c3, int c4, int prevColor, int prevSize){ if(c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) return (prevC...

Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only. I thought so because in the sample input we have: 0 0 2 0 0 2 1 1 3 3 2 3 and answer is no although they've a common area (infinite non integer points)! can you p...

During the contest i got AC using the following recursion get(firstGroupColor, firstGroupSize,firstColorAvaiable,secondColorAvaiable, thirdColorAvaiable,fourthColorAvaiable, prevGroupColor, prevGroupSize) = { num = 0; for(each color i from 1 to 4) for(each size j from 1 to avaialable of color i) if(...

I'm a bit confused about this problem, does interior point means a lattice point or just an a common area? I assume the first, so shouldn't this testcase output no (I see that you output yes for it)?

0 0 1 0 1 1
0 0 1 0 1 1

Very interesting solution thanks alot. by the way I can't find Karp's algorithm in Cormen, is it really there? (actually I looked in the index and found nothing except for an excecise talking about minimum mean cycle).

Thanks alot it helped very much, I got AC after getting over a couple of things, 1- The Karp's pseudo code in the paper has a mistake in line 10, we should set lamda to a small value instead of INF. 2- I've applied Kosaraju's Algorithm for SCC as you've advised. by the way do you know if these algor...