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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...