1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11373 - Happy Birthday
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=25&page=show_problem&problem=2368
*
* @author Felix Dietrich
* @version 1.0, 06/07/2010
*
* Method : Romberg integration
* Status : WA :((
* Runtime:
*/


import java.util.*;
import java.lang.*;

class Main
{
static abstract class Func<T,U>
{
public double[] args;
public Func<Double,Double> f;

public Func()
{
}

public Func(double... args)
{
this.args = args;
}

public Func(Func<Double,Double> f, double... args)
{
this.args = args;
this.f = f;
}

public abstract U apply(T... arguments);
}

/**
Performs a romberg method approximation for the integral of the given function.
@param f function to integrate
@param a left border
@param b right border
@param iterSteps 0...n iteration step number
*/
public static double RombergIntegration(Func<Double,Double> f, double a, double b, int iterSteps)
{
if(a > b)
{
double tmp = a;
a = b;
b = tmp;
}

System.out.printf("Integrating from %f to %f...\n", a,b);

Func<Double,Double> T0 = new Func<Double,Double>(f,a,b)
{
public Double apply(Double... args)
{
double a = this.args[0];
double b = this.args[1];
Func<Double,Double> f = this.f;

double H = args[0];
int n = (int)((b-a)/H);
double sum=0;

for(int i=1; i<=n-1; i++)
sum += f.apply(a+i*H);

return H/2*(f.apply(a)+f.apply(b))+H*(sum);
}
};

Func<Double,Double> Ti = new Func<Double,Double>(T0)
{
public Double apply(Double... args)
{
Func<Double,Double> T0 = this.f;

double H = args[0];
double i = args[1];
double pow2_2i = Math.pow(2,2*i);

if(i == 0.0)
return T0.apply(H);
else
return (pow2_2i*apply(H/2,i-1)-apply(H,i-1))/(pow2_2i-1);
}
};

return Ti.apply((b-a)/1.0, (double)iterSteps);
}

public static void main(String... args)
{
Scanner sc = new Scanner(System.in);

int R,h;
double ax,ay,bx,by;
double cx,cy,dx,dy;
double l1,l2;
double px,py;
double phiA,phiB,phiC,phiD;
double phiAD,phiDB,phiBC,phiCA;
double A,B,C,D;

while(sc.hasNext())
{
R = sc.nextInt();
h = sc.nextInt();
ax = sc.nextInt();
ay = sc.nextInt();
bx = sc.nextInt();
by = sc.nextInt();
cx = sc.nextInt();
cy = sc.nextInt();
dx = sc.nextInt();
dy = sc.nextInt();

l2 = (cy+(ax*(dy-cy)-cx*(dy-cy))/(dx-cx)-ay)/(by-ay-(bx-ax)*(dy-cy)/(dx-cx));
l1 = (ax+(bx-ax)*l2-cx)/(dx-cx);

px = ax+(bx-ax)*l2;
py = ay+(by-ay)*l2;

ax = ax-px;
bx = bx-px;
cx = cx-px;
dx = dx-px;
ay = ay-py;
by = by-py;
cy = cy-py;
dy = dy-py;

phiA = Math.acos(Math.abs(ax+px)/Math.hypot(ax+px,ay+py));
phiC = (Math.atan2(cy-py,cx-px)+2*Math.PI)%(2*Math.PI);
phiB = (Math.atan2(by-py,bx-px)+2*Math.PI)%(2*Math.PI);
phiD = (Math.atan2(dy-py,dx-px)+2*Math.PI)%(2*Math.PI);

phiAD = Math.acos(Math.abs(ax*dx+ay*dy)/(Math.hypot(ax,ay)*Math.hypot(dx,dy)));
phiDB = Math.acos(Math.abs(dx*bx+dy*by)/(Math.hypot(dx,dy)*Math.hypot(bx,by)));
phiBC = Math.acos(Math.abs(bx*cx+by*cy)/(Math.hypot(bx,by)*Math.hypot(cx,cy)));
phiCA = Math.acos(Math.abs(cx*ax+cy*ay)/(Math.hypot(cx,cy)*Math.hypot(ax,ay)));

System.out.printf("phi a: %f\n", phiA);
System.out.printf("phi b: %f\n", phiB);
System.out.printf("phi c: %f\n", phiC);
System.out.printf("phi d: %f\n", phiD);
System.out.printf("phi ad: %f\n", phiAD);
System.out.printf("phi db: %f\n", phiDB);
System.out.printf("phi bc: %f\n", phiBC);
System.out.printf("phi ca: %f\n", phiCA);

Func<Double,Double> f = new Func<Double,Double>(px,py,R)
{
public Double apply(Double... x)
{
double px = this.args[0];
double py = this.args[1];
double R = this.args[2];
return Math.hypot(R*Math.cos(x[0])-px,R*Math.sin(x[0])-py);
}
};

A = RombergIntegration(f, phiA, phiC, 8)*R/2;
B = RombergIntegration(f, phiC, phiB, 8)*R/2;
C = RombergIntegration(f, phiB, phiD, 8)*R/2;
D = RombergIntegration(f, phiD, phiA, 8)*R/2;

List<Double> l = new ArrayList<Double>();
l.add(A);
l.add(B);
l.add(C);
l.add(D);
Collections.sort(l);

System.out.printf("%.02f %.02f\n", (l.get(3)*h), (l.get(0)*h));
}
}
}