EvbCFfp1XB

problem and my answer.

October 2012

import java.util.HashMap;

/**
* Chapter 24. Elementary Geometric Methods - Problem4 - Robert Sedgewick
* Algorithms in C++<br>
* 線分の配列が与えられた時、それらが単純な閉じた多角形を形作るかどうかを判定するにはどうしたらよいか。
*/
public class Chapter24ElementaryGeometricMethodsProblem4 {
public static void main(String[] args) {
depthFirstSearch(0, new int[12]);
}

private static void depthFirstSearch(int i, int[] a) {
if (i >= 12) {
Line l0 = new Line(new Point(a[0], a[1]), new Point(a[2], a[3]));
Line l1 = new Line(new Point(a[4], a[5]), new Point(a[6], a[7]));
Line l2 = new Line(new Point(a[8], a[9]), new Point(a[10], a[11]));
if (isSimpleClosedPolygon(new Line[] { l0, l1, l2, })) {
System.out
.format("(%d, %d), (%d, %d), (%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
l0.p1.x, l0.p1.y, l0.p2.x, l0.p2.y, l1.p1.x,
l1.p1.y, l1.p2.x, l1.p2.y, l2.p1.x, l2.p1.y,
l2.p2.x, l2.p2.y);
}
return;
}

for (int j = 0; j < 3; j++) {
a[i] = j;
depthFirstSearch(i + 1, a);
}
}

private static boolean isSimpleClosedPolygon(Line[] lines) {
HashMap<Point, Integer> map = new HashMap<Point, Integer>();
for (int i = 0; i < lines.length; i++) {
{
Integer count = map.get(lines[i].p1);
map.put(lines[i].p1, count == null ? 1 : (count + 1));
}
{
Integer count = map.get(lines[i].p2);
map.put(lines[i].p2, count == null ? 1 : (count + 1));
}
}
for (Point p : map.keySet()) {
if (map.get(p) % 2 == 0) {
} else {
return false;
}
}
return true;
}

private static class Line {
private Point p1;
private Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

private static class Point {
private int x;
private int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
}
}

/**
* Chapter 24. Elementary Geometric Methods - Problem3 - Robert Sedgewick
* Algorithms in C++<br>
* 4本の線分が正方形を形作るかどうかを判定する、割り算を使わない高速なアルゴリズムを導け。
*/
public class Chapter24ElementaryGeometricMethodsProblem3 {
public static void main(String[] args) {
int max = 3;
for (int x0 = 0; x0 < max; x0++) {
for (int y0 = 0; y0 < max; y0++) {
Point p0 = new Point(x0, y0);
for (int x1 = 0; x1 < max; x1++) {
for (int y1 = 0; y1 < max; y1++) {
Point p1 = new Point(x1, y1);
for (int x2 = 0; x2 < max; x2++) {
for (int y2 = 0; y2 < max; y2++) {
Point p2 = new Point(x2, y2);
for (int x3 = 0; x3 < max; x3++) {
for (int y3 = 0; y3 < max; y3++) {
Point p3 = new Point(x3, y3);
Line l0 = new Line(p0, p1);
Line l1 = new Line(p1, p2);
Line l2 = new Line(p2, p3);
Line l3 = new Line(p3, p0);
if (isSquare(new Line[] { l0, l1, l2,
l3, })) {
System.out
.format("(%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
p0.x, p0.y, p1.x,
p1.y, p2.x, p2.y,
p3.x, p3.y);
}
}
}
}
}
}
}
}
}
}

private static boolean isSquare(Line[] lines) {
for (int i = 0; i < 4; i++) {
int dx1 = lines[i].p2.x - lines[i].p1.x;
int dy1 = lines[i].p2.y - lines[i].p1.y;
int dx2 = lines[(i + 1) % 4].p2.x - lines[(i + 1) % 4].p1.x;
int dy2 = lines[(i + 1) % 4].p2.y - lines[(i + 1) % 4].p1.y;
int dx3 = lines[(i + 1) % 4].p2.x - lines[i].p1.x;
int dy3 = lines[(i + 1) % 4].p2.y - lines[i].p1.y;
int d1 = dx1 * dx1 + dy1 * dy1;
int d2 = dx2 * dx2 + dy2 * dy2;
int d3 = dx3 * dx3 + dy3 * dy3;
if (d1 == d2 && d1 + d2 == d3) {
} else {
return false;
}
}
return true;
}

private static class Line {
private Point p1;
private Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

private static class Point {
private int x;
private int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}

/**
* Chapter 24. Elementary Geometric Methods - Problem2 - Robert Sedgewick
* Algorithms in C++<br>
* 2本の線分が平行かどうかを判定する、割り算を使わない高速なアルゴリズムを導け。
*/
public class Chapter24ElementaryGeometricMethodsProblem2 {
public static void main(String[] args) {
int max = 4;
for (int x0 = 0; x0 < max; x0++) {
for (int y0 = 0; y0 < max; y0++) {
Point p0 = new Point(x0, y0);
for (int x1 = 0; x1 < max; x1++) {
for (int y1 = 0; y1 < max; y1++) {
Point p1 = new Point(x1, y1);
for (int x2 = 0; x2 < max; x2++) {
for (int y2 = 0; y2 < max; y2++) {
Point p2 = new Point(x2, y2);
for (int x3 = 0; x3 < max; x3++) {
for (int y3 = 0; y3 < max; y3++) {
Point p3 = new Point(x3, y3);
Line l1 = new Line(p0, p1);
Line l2 = new Line(p2, p3);
if (isParallel(l1, l2)) {
System.out
.format("(%d, %d), (%d, %d), (%d, %d), (%d, %d)\n",
l1.p1.x, l1.p1.y,
l1.p2.x, l1.p2.y,
l2.p1.x, l2.p1.y,
l2.p2.x, l2.p2.y);
}
}
}
}
}
}
}
}
}
}

private static boolean isParallel(Line l1, Line l2) {
int dy1 = l1.p2.y - l1.p1.y;
int dx2 = l2.p2.x - l2.p1.x;
int dy2 = l2.p2.y - l2.p1.y;
int dx1 = l1.p2.x - l1.p1.x;
// return dy1 / dx1 == dy2 / dx2;
return dy1 * dx2 == dy2 * dx1;
}

private static class Line {
private Point p1;
private Point p2;

public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}

private static class Point {
private int x;
private int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}

/**
* Chapter 24. Elementary Geometric Methods - Problem1 - Robert Sedgewick
* Algorithms in C++<br>
* 関数 ccw の値を、2点が同一で残りの1点が異なるような3通りの場合と、3点とも同一な場合について求めよ。
*/
public class Chapter24ElementaryGeometricMethodsProblem1 {
public static void main(String[] args) {
Point p0 = new Point(randomInt(-10000, 10000), randomInt(-10000, 10000));
Point p1 = new Point(randomInt(-10000, 10000), randomInt(-10000, 10000));
System.out.format("p0 = (%d, %d)\n", p0.x, p0.y);
System.out.format("p1 = (%d, %d)\n", p1.x, p1.y);
System.out.format("ccw(p0, p0, p1) = %d\n", ccw(p0, p0, p1));
System.out.format("ccw(p0, p1, p0) = %d\n", ccw(p0, p1, p0));
System.out.format("ccw(p1, p0, p0) = %d\n", ccw(p1, p0, p0));
System.out.format("ccw(p0, p0, p0) = %d\n", ccw(p0, p0, p0));
}

private static int randomInt(int min, int max) {
return min + (int) (((max + 1) - min) * Math.random());
}

private static class Point {
private int x;
private int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

private static int ccw(Point p0, Point p1, Point p2) {
int dx1 = p1.x - p0.x;
int dy1 = p1.y - p0.y;
int dx2 = p2.x - p0.x;
int dy2 = p2.y - p0.y;
System.out.format("dx1=%d, dy1=%d, dx2=%d, dy2=%d\n", dx1, dy1, dx2,
dy2);
System.out.format("dx1 * dy2 = %d , dy1 * dx2 = %d\n", dx1 * dy2, dy1
* dx2);
if (dx1 * dy2 > dy1 * dx2) {
return 1;
}
System.out.format("dx1 * dy2 = %d , dy1 * dx2 = %d\n", dx1 * dy2, dy1
* dx2);
if (dx1 * dy2 < dy1 * dx2) {
return -1;
}
System.out.format("dx1 * dx2 = %d , dy1 * dy2 = %d\n", dx1 * dx2, dy1
* dy2);
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) {
return -1;
}
System.out
.format("(dx1 * dx1 + dy1 * dy1) = %d , (dx2 * dx2 + dy2 * dy2) = %d\n",
(dx1 * dx1 + dy1 * dy1), (dx2 * dx2 + dy2 * dy2));
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) {
return 1;
}
return 0;
}
}

problem 1053:   Accelerated Railgun

how to solve This problem is easy, right?

source code

import java.util.Scanner;

public class AcceleratedRailgun {
private static boolean test = !true;

public static void main(String[] args) {
if (test) {
testA();
testB();
testC();
testD();
testE();
testF();
testG();
testZ();
} else {
run();
}
}

private static void testA() {
String id = "A";
String input = "10.0\n" + "0.5 0.0 -0.2 0.0\n";
String output = "0.50000000";
test(id, input, output);
}

private static void testB() {
String id = "B";
String input = "1.0\n" + "0.1 0.0 0.2 0.2\n";
String output = "impossible";
test(id, input, output);
}

private static void testC() {
String id = "C";
String input = "10.0\n" + "0.0 " + Math.sin(Math.PI / 4d)
+ " 1.0 0.0\n";
String output = "impossible";
test(id, input, output);
}

private static void testD() {
String id = "D";
String input = "10.0\n" + "1.0 0.0 -1.0 1.0\n";
String output = "impossible";
test(id, input, output);
}

private static void testE() {
String id = "E";
String input = "0.49\n" + "0.5 0.0 -0.2 0.0\n";
String output = "impossible";
test(id, input, output);
}

private static void testF() {
String id = "F";
String input = "2.0\n" + "0.5 0.0 0.2 0.0\n";
String output = "1.5";
test(id, input, output);
}

private static void testG() {
String id = "G";
String input = "47.799187848899734\n"
+ "0.14591853123569276 -0.43052220061326985 -0.3046551909551817 0.03139441106722973";
String output = "I'm not sure.";
test(id, input, output);
}

private static void testZ() {
String id = "Z";
double a;
double b;
double c;
double d;
for (;;) {
a = randomDouble(-1, 1);
b = randomDouble(-1, 1);
c = randomDouble(-1, 1);
d = randomDouble(-1, 1);
if (hypot(a, b) <= 1 && hypot(c, d) <= 1) {
break;
}
}
String input = "" + randomDouble(1, 50) + "\n" + "" + a + " " + b + " "
+ c + " " + d;
System.out.format("%s\n", input);
String output = "I'm not sure.";
test(id, input, output);
}

private static double randomDouble(int min, int max) {
return min + (max - min) * Math.random();
}

private static void test(String id, String input, String output) {
long start = System.nanoTime();
String result = run(input);
if (output.equals("impossible") || result.equals("impossible")) {
System.out.format("(%s)", output.equals(result) ? id : id + " "
+ "expected:<" + output + "> but was:<" + result + ">");
} else {
System.out.format(
"(%s)",
Math.abs(Double.parseDouble(output)
- Double.parseDouble(result)) < 1.0e-6 ? id : id
+ " " + "expected:<" + output + "> but was:<"
+ result + ">");
}
System.out.format("[%.2f]\n", (System.nanoTime() - start) / 1e9);
}

private static String run(String input) {
Scanner sc = new Scanner(input);
double D = sc.nextDouble();
double px = sc.nextDouble();
double py = sc.nextDouble();
double vx = sc.nextDouble();
double vy = sc.nextDouble();
String result = solve(D, px, py, vx, vy);
sc.close();
return result;
}

private static void run() {
Scanner sc = new Scanner(System.in);
for (; sc.hasNext();) {
double D = sc.nextDouble();
if (D == 0) {
break;
}
double px = sc.nextDouble();
double py = sc.nextDouble();
double vx = sc.nextDouble();
double vy = sc.nextDouble();
String result = solve(D, px, py, vx, vy);
System.out.print(result + "\n");
}
sc.close();
}

private static String solve(double D, double startx, double starty,
double vx, double vy) {
for (double distance = 0; distance <= D;) {
double r = hypot(vx, vy);
vx = 2 / r * vx;
vy = 2 / r * vy;
double endx = startx + vx;
double endy = starty + vy;
if (isOnLine(0, 0, startx, starty, endx, endy)
&& isInRectangle(0, 0, startx, starty, endx, endy)) {
double d2 = distance + hypot(startx - 0, starty - 0);
if (d2 <= D) {
return Double.toString(d2);
} else {
return "impossible";
}
}
double[][] is = intersectionOfCircleAndLine(0, 0, 1, startx,
starty, endx, endy);
double[] intersection;
if (hypot(is[0][0] - endx, is[0][1] - endy) < hypot(
is[1][0] - endx, is[1][1] - endy)) {
intersection = is[0];
} else {
intersection = is[1];
}
double[] symmetric = symmetricPointOfLine(startx, starty, 0, 0,
intersection[0], intersection[1]);
distance += hypot(intersection[0] - startx, intersection[1]
- starty);
startx = intersection[0];
starty = intersection[1];
vx = symmetric[0] - startx;
vy = symmetric[1] - starty;
}

return "impossible";
}

/**
* (px, py) is a point.<br>
* (l0x, l0y) and (l1x, l1y) are two points on the line.
*/
private static double[] symmetricPointOfLine(double px, double py, int l0x,
int l0y, double l1x, double l1y) {
double[] nearest = nearestPointOfLine(px, py, l0x, l0y, l1x, l1y);
return new double[] { 2 * (nearest[0] - px) + px,
2 * (nearest[1] - py) + py, };
}

/**
* (px, py) is a point.<br>
* (r0x, r0y) and (r1x, r1y) are two points of the rectangle.
*/
private static boolean isInRectangle(double px, double py, double r0x,
double r0y, double r1x, double r1y) {
return px >= Math.min(r0x, r1x) && px <= Math.max(r0x, r1x)
&& py >= Math.min(r0y, r1y) && py <= Math.max(r0y, r1y);
}

/**
* (px, py) is a point.<br>
* (l0x, l0y) and (l1x, l1y) are two points on the line.
*/
private static boolean isOnLine(double px, double py, double l0x,
double l0y, double l1x, double l1y) {
// linear equation : (y - l0y) == (l1y - l0y) / (l1x - l0x) * (x - l0x)
// (l1x - l0x) * (y - l0y) == (l1y - l0y) * (x - l0x)
// (l1x - l0x) * (y - l0y) - (l1y - l0y) * (x - l0x) == 0
double abs = Math.abs((l1x - l0x) * (py - l0y) - (l1y - l0y)
* (px - l0x));
return abs <= 1e-10;
}

/**
* (px, py) is a point.<br>
* (l0x, l0y) and (l1x, l1y) are two points on the line.
*/
private static double[] nearestPointOfLine(double px, double py,
double l0x, double l0y, double l1x, double l1y) {
if (Math.abs(l0x - l1x) <= 1e-10) {
return new double[] { l0x, py };
}
if (Math.abs(l0y - l1y) <= 1e-10) {
return new double[] { px, l0y };
}
// linear equation : (y - l0y) == (l1y - l0y) / (l1x - l0x) * (x - l0x)
// y == (l1y - l0y) / (l1x - l0x) * (x - l0x) + l0y
double d = (l1y - l0y) / (l1x - l0x);
// y == d * (x - l0x) + l0y
// normal line : y == (-1 / d) * (x - px) + py
// d * (x - l0x) + l0y == (-1 / d) * (x - px) + py
// d * x - d * l0x + l0y == (-1 / d) * x - (-1 / d) * px + py
// d * x - (-1 / d) * x == d * l0x - l0y - (-1 / d) * px + py
// (d - (-1 / d)) * x == d * l0x - l0y - (-1 / d) * px + py
// x == (d * l0x - l0y - (-1 / d) * px + py) / (d - (-1 / d))
double x = (d * l0x - l0y - (-1 / d) * px + py) / (d - (-1 / d));
return new double[] { x, d * (x - l0x) + l0y };
}

/**
* (cx, cy) is the center of the circle.<br>
* cr is the radius of the circle.<br>
* (l0x, l0y) and (l1x, l1y) are two points on the line.
*/
private static double[][] intersectionOfCircleAndLine(int cx, int cy,
int cr, double l0x, double l0y, double l1x, double l1y) {
if (Math.abs(l0y - l1y) <= 1e-10) {
// line : y == l0y
// circle : (x - cx) * (x - cx) + (y - cy) * (y - cy) == cr * cr
// (x - cx) * (x - cx) + (l0y - cy) * (l0y - cy) == cr * cr
double d = l0y - cy;
// (x - cx) * (x - cx) + d * d == cr * cr
// x * x -2 * cx * x + cx * cx + d * d == cr * cr
// x * x -2 * cx * x + cx * cx + d * d - cr * cr == 0
double[] x = quadraticFormula(1, -2 * cx, cx * cx + d * d - cr * cr);
return new double[][] { { x[0], l0y, }, { x[1], l0y, }, };
}
if (Math.abs(l0x - l1x) <= 1e-10) {
// line : x == l0x
// circle : (x - cx) * (x - cx) + (y - cy) * (y - cy) == cr * cr
// (l0x - cx) * (l0x - cx) + (y - cy) * (y - cy) == cr * cr
double d = l0x - cx;
// d * d + (y - cy) * (y - cy) == cr * cr
// d * d + y * y -2 * cy * y + cy * cy == cr * cr
// y * y -2 * cy * y + cy * cy + d * d - cr * cr == 0
double[] y = quadraticFormula(1, -2 * cy, cy * cy + d * d - cr * cr);
return new double[][] { { l0x, y[0], }, { l0x, y[1], }, };
}

{
// linear equation : (y - l0y) == (l1y - l0y) / (l1x - l0x) * (x -
// l0x)
double a = (l1y - l0y) / (l1x - l0x);
// (y - l0y) == a * (x - l0x)
// y == a * (x - l0x) + l0y
// y == a * x - a * l0x + l0y
double b = -a * l0x + l0y;
// y == a * x + b
// circle : (x - cx) * (x - cx) + (y - cy) * (y - cy) == cr * cr
// (x - cx) * (x - cx) + (a * x + b - cy) * (a * x + b - cy) == cr *
// cr
double c = b - cy;
// (x - cx) * (x - cx) + (a * x + c) * (a * x + c) == cr * cr
// x * x -2 * cx * x + cx * cx + a * a * x * x + 2 * a * c * x + c *
// c == cr * cr
// (1 + a * a) * x * x + (-2 * cx + 2 * a * c) * x + (cx * cx + c *
// c - cr * cr) == 0
double[] x = quadraticFormula(1 + a * a, -2 * cx + 2 * a * c, cx
* cx + c * c - cr * cr);
return new double[][] { { x[0], a * x[0] + b, },
{ x[1], a * x[1] + b, }, };
}
}

private static double[] quadraticFormula(double a, double b, double c) {
double d = Math.sqrt(b * b - 4 * a * c);
return new double[] { (-b + d) / (2 * a), (-b - d) / (2 * a), };
}

private static double hypot(double x, double y) {
return Math.sqrt(x * x + y * y);
}
}

このページのトップヘ