OJ Board

You may find this O(n) algorithm interesting (no need to know how many color there are).
http://citeseer.ist.psu.edu/494676.html

Thanks. I got it.

How do you prove the greedy is always correct?

Yes, you are right. My AC output is the same as yours.

I used a nlogn algorithm for finding median. Is there any better algorithm?

AC Finally. Thank you all. Just "guess" the constant.

The first product is ln2 but i still don't know what is the value of ln(1+x^2)/(x+1)dx

I read a paper and it said that :
For a n-gon (n>=5), there is no way to dissect it into m triangles with equal area with gcd(n,m)=1.

AC now after using string to read input!!!

My output has the same number of moves as your output. Could you please check what's wrong with my code :
#include <iostream>
#define MAXK 1005
#define MAXP 15
#define MAXQ 15
using namespace std;
int m,n,k,p,q,x0,y0,k0;
bool c[MAXK][MAXK];
int pq[MAXK*(MAXP+1)*(2*MAXQ+1)*3];
int d[MAXK],a[MAXK ...

Could someone give me the output for this input?
20

31 31 9 4
0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 ...

In the case where n is odd, it should be :

i change your program to compute the condition for all 3 edges of the triangle and it got AC:
bool valid(double a, double b, double c, double d){
double theta, alpha, eta, xx;
if( a - d > eps ) return false ;

theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;

alpha = acos( a/d ); // since D[j ...

It's the same as my AC code and i only considers flight (i,j) where i<j.

theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;
alpha = acos( a/D[j] ); // since D[j] = 2*r ;
I believe that you have used the wrong angle.
I used this one
theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ;
alpha = asin(c/D[j] );
if (alpha-theta>-eps) ...
And you used it for all 3 edges of the triangle ...