1.
/**
* FWP: Ausgewaehlte Probleme aus dem ACM
*
* Problem: 11373 - Happy Birthday
* URL: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=25&problem=2368
* Method: Geometry
* Accepted: 0.156
* Date: 21.10.2010
* @author Evgeni Pavlidis
*
*
* References:
* http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
* http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/
* http://en.wikipedia.org/wiki/Circle_segment
*/
import java.io.*;
import java.util.*;
class Main {
static class Point
{
double x,y;
Point(double x, double y)
{ this.x = x; this.y = y; }
double dist(Point o)
{ return Math.sqrt((x - o.x)*(x - o.x) + (y + o.y)*(y + o.y)); }
public String toString()
{ return "(" + x + ", " + y + ")"; }
}
// save points for lines p and q
static Point p1,p2,q1,q2;
// intersection point between the two lines (inside circle)
static Point s;
// save intersection points with the circle and two lines
static Point[] c = new Point[4];
static double h,r, max,min;
static Point m = new Point(0,0);
static Point lineLineIntersection(Point p1, Point p2, Point q1, Point q2)
{
double u;
u = ((q2.x - q1.x)*(p1.y - q1.y) - (q2.y - q1.y)*(p1.x - q1.x)) /
((q2.y - q1.y)*(p2.x - p1.x) - (q2.x - q1.x)*(p2.y - p1.y));
Point result = new Point(p1.x + u * (p2.x - p1.x),p1.y + u * (p2.y - p1.y));
return result;
}
// calc intersection points of the circle and a line(p) and return them as r1 and r2
static void lineCircleIntersection(Point p1, Point p2, Point r1, Point r2)
{
double a,b,c,u1,u2;
a = (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
b = 2 * ((p2.x - p1.x)*p1.x + (p2.y - p1.y)*p1.y);
c = p1.x*p1.x + p1.y*p1.y - r*r;
u1 = (-b + Math.sqrt(b*b - 4*a*c)) / (2*a);
u2 = (-b - Math.sqrt(b*b - 4*a*c)) / (2*a);
r1.x = p1.x + u1*(p2.x - p1.x);
r1.y = p1.y + u1*(p2.y - p1.y);
r2.x = p1.x + u2*(p2.x - p1.x);
r2.y = p1.y + u2*(p2.y - p1.y);
}
static double triangleArea(Point a, Point b, Point c)
{ return Math.abs((b.x*a.y-a.x*b.y)+(c.x*b.y-b.x*c.y)+(a.x*c.y-c.x*a.y)) / 2; }
static double crossProduct(Point m, Point a, Point b)
{ return (a.x - m.x)*(b.y - m.y) - (b.x - m.x)*(a.y - m.y); }
static double dotProduct(Point m, Point a, Point b)
{ return (a.x - m.x)*(b.x - m.x) + (a.y - m.y)*(b.y - m.y); }
static double segmentArea(Point m, Point a, Point b)
{
double alpha = Math.acos(dotProduct(m,a,b)/(a.dist(m)*b.dist(m)));
return r*r / 2 * (alpha - Math.sin(alpha));
}
public static void main(String...args)
{
Scanner sc = new Scanner(System.in);
// init
for(int i = 0; i < 4; i++)
c[i] = new Point(-1000, -1000);
while(sc.hasNextInt())
{
max = Double.MIN_VALUE;
min = Double.MAX_VALUE;
r = sc.nextInt();
h = sc.nextInt();
p1 = new Point(sc.nextInt(),sc.nextInt());
p2 = new Point(sc.nextInt(),sc.nextInt());
q1 = new Point(sc.nextInt(),sc.nextInt());
q2 = new Point(sc.nextInt(),sc.nextInt());
s = lineLineIntersection(p1,p2,q1,q2);
lineCircleIntersection(p1,p2, c[0], c[2]);
lineCircleIntersection(q1,q2, c[1], c[3]);
double area;
for(int i = 0; i < 4; i++)
{
area = triangleArea(s, c[i], c[(i+1)%4]);
// check if middle point (m = (0,0)) and intersection point (s) lie on the same side of the segment line
if(crossProduct(c[i], c[(i+1)%4], s) * crossProduct(c[i],c[(i+1)%4], m) > 0)
area += segmentArea(m, c[i], c[(i+1)%4]);
else
area += r*r*Math.PI - segmentArea(m, c[i], c[(i+1)%4]);
if(area > max)
max = area;
if(area < min)
min = area;
}
System.out.printf("%.2f %.2f\n", max*h, min*h);
}
}
}
2.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11373 Happy Birthday
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2368
*
* @author Anton Pavlushko, IBB7B,
* @version 1.0, 06/11/2010
*
* Status : Accepted
* Runtime: 0.132
*/
import java.io.*;
import java.util.*;
public class Main {
public static double get_length(double ax,double ay,double bx,double by) {
return Math.sqrt(Math.pow(ax-bx,2)+Math.pow(ay-by,2));
}
public static double get_square(double a,double b,double c) {
return Math.sqrt((a+b+c)*(b+c-a)*(a+c-b)*(a+b-c))/4;
}
public static double get_sector(double radius,double length) {
return 2*(Math.PI/2-Math.acos(length/(2*radius)))*radius*radius/2-(length/2)*Math.sqrt(radius*radius-length*length/4);
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String current_line, empty = "";
int number, border, i, j, length, number_local;
int primes [];
Iterator iter;
int radius,height;
StringTokenizer input_string;
int a[],b[],c[],d[],line_count,d_count,e_count,f_count;
double ab[],cd[],e[],ab_centre[],cd_centre[],a_real[],b_real[],c_real[],d_real[],distance[],squares[],
ac_width,ad_width,bc_width,bd_width,ea_width,eb_width,ec_width,ed_width,minimum,maximum;
try {
while ((current_line=in.readLine())!= null && !current_line.equals("0")) {
input_string = new StringTokenizer(current_line);
// input_string = new StringTokenizer("10 5");
radius=Integer.parseInt(input_string.nextToken());
height=Integer.parseInt(input_string.nextToken());
ab = new double[3];
cd = new double[3];
current_line=in.readLine();
input_string = new StringTokenizer(current_line);
// input_string = new StringTokenizer("-10 0 10 0");
a = new int[2]; for(i=0;i<2;i++) a[i]=Integer.parseInt(input_string.nextToken());
b = new int[2]; for(i=0;i<2;i++) b[i]=Integer.parseInt(input_string.nextToken());
current_line=in.readLine();
input_string = new StringTokenizer(current_line);
// input_string = new StringTokenizer("-6 8 6 -8");
c = new int[2]; for(i=0;i<2;i++) c[i]=Integer.parseInt(input_string.nextToken());
d = new int[2]; for(i=0;i<2;i++) d[i]=Integer.parseInt(input_string.nextToken());
ab[0]=a[1]-b[1];
ab[1]=b[0]-a[0];
ab[2]=a[0]*b[1]-b[0]*a[1];
cd[0]=c[1]-d[1];
cd[1]=d[0]-c[0];
cd[2]=c[0]*d[1]-d[0]*c[1];
e = new double[2];
e[0]=-(ab[2]*cd[1]-cd[2]*ab[1])/(ab[0]*cd[1]-cd[0]*ab[1]);
e[1]=-(ab[0]*cd[2]-cd[0]*ab[2])/(ab[0]*cd[1]-cd[0]*ab[1]);
ab_centre = new double[2];
ab_centre[0]=-ab[0]*ab[2]/(Math.pow(ab[0],2)+Math.pow(ab[1],2));
ab_centre[1]=-ab[1]*ab[2]/(Math.pow(ab[0],2)+Math.pow(ab[1],2));
cd_centre = new double[2];
cd_centre[0]=-cd[0]*cd[2]/(Math.pow(cd[0],2)+Math.pow(cd[1],2));
cd_centre[1]=-cd[1]*cd[2]/(Math.pow(cd[0],2)+Math.pow(cd[1],2));
distance = new double[2];
distance[0]=Math.sqrt(radius*radius-ab[2]*ab[2]/(Math.pow(ab[0],2)+Math.pow(ab[1],2)));
distance[1]=Math.sqrt(radius*radius-cd[2]*cd[2]/(Math.pow(cd[0],2)+Math.pow(cd[1],2)));
distance[0]=Math.sqrt(distance[0]*distance[0]/(Math.pow(ab[0],2)+Math.pow(ab[1],2)));
distance[1]=Math.sqrt(distance[1]*distance[1]/(Math.pow(cd[0],2)+Math.pow(cd[1],2)));
a_real = new double[2];
b_real = new double[2];
c_real = new double[2];
d_real = new double[2];
a_real[0]=ab_centre[0]+ab[1]*distance[0];
a_real[1]=ab_centre[1]-ab[0]*distance[0];
b_real[0]=ab_centre[0]-ab[1]*distance[0];
b_real[1]=ab_centre[1]+ab[0]*distance[0];
c_real[0]=cd_centre[0]+cd[1]*distance[1];
c_real[1]=cd_centre[1]-cd[0]*distance[1];
d_real[0]=cd_centre[0]-cd[1]*distance[1];
d_real[1]=cd_centre[1]+cd[0]*distance[1];
ac_width=Main.get_length(a_real[0],a_real[1],c_real[0],c_real[1]);
ad_width=Main.get_length(a_real[0],a_real[1],d_real[0],d_real[1]);
bc_width=Main.get_length(b_real[0],b_real[1],c_real[0],c_real[1]);
bd_width=Main.get_length(b_real[0],b_real[1],d_real[0],d_real[1]);
ea_width=Main.get_length(e[0],e[1],a_real[0],a_real[1]);
eb_width=Main.get_length(e[0],e[1],b_real[0],b_real[1]);
ec_width=Main.get_length(e[0],e[1],c_real[0],c_real[1]);
ed_width=Main.get_length(e[0],e[1],d_real[0],d_real[1]);
squares = new double[4];
squares[0]=Main.get_square(ac_width,ec_width,ea_width)+Main.get_sector(radius,ac_width);//EAC
squares[1]=Main.get_square(ad_width,ea_width,ed_width)+Main.get_sector(radius,ad_width);//AED
squares[2]=Main.get_square(bd_width,eb_width,ed_width)+Main.get_sector(radius,bd_width);//BED
squares[3]=Main.get_square(bc_width,ec_width,eb_width)+Main.get_sector(radius,bc_width);//CEB
minimum=Math.PI*radius*radius;
maximum=0;
if (squares[0]+squares[1]+squares[2]+squares[3]!=minimum) {
j=0;
for(i=0;i<4;i++) {
if (maximum<squares[i]) {
j=i;
maximum=squares[i];
}
}
squares[j]=Math.PI*radius*radius;
for(i=0;i<4;i++) {
if (i!=j) squares[j]=squares[j]-squares[i];
}
}
minimum=Math.PI*radius*radius;
maximum=0;
for(i=0;i<4;i++) {
if (minimum>squares[i]) minimum=squares[i];
if (maximum<squares[i]) maximum=squares[i];
}
maximum=maximum*height;
minimum=minimum*height;
Formatter formatter = new Formatter();
formatter.format(Locale.US, "%.2f %.2f",maximum,minimum);
System.out.println(formatter.toString());
}//while
} // end try
catch (IOException ee) {
System.err.println("Error: " + ee);
}
}
}
3.
/**
* 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));
}
}
}