The Java Program: D_angles/YiuEqualAngles.java
1
2
3
4
5
6
7
8 import java.io.*;
9 import java.util.*;
10 import java.text.*;
11
12 public class YiuEqualAngles
13 {
14 private static DecimalFormat fmt = new DecimalFormat("0.00");
15 private static double tol = 1e-9;
16
17 public Scanner in;;
18 public PrintStream out;
19
20 public void main() throws Exception
21 {
22 Pair A, B, C, P, Q;
23 in = new Scanner( new File( "equalangles.in" ) );
24 out = new PrintStream( new FileOutputStream( "equalanglesyiu.out" ) );
25
26 int[] v = input();
27 while(v != null)
28 {
29 A = new Pair(v[0], v[1]);
30 B = new Pair(v[2], v[3]);
31 C = new Pair(v[4], v[5]);
32
33 P = calc(A, B, C);
34 Q = calc(A, C, B);
35
36 out.println(P + " " + Q);
37
38 v = input();
39 }
40 }
41
42 public int[] input()
43 {
44 boolean EOF = true;
45 int[] res = new int[6];
46 for(int i = 0; i < 6; ++i)
47 {
48 res[i] = in.nextInt();
49 if(res[i] != 0) EOF = false;
50 }
51
52 return (EOF ? null : res);
53 }
54
55 public Pair calc(Pair A, Pair B, Pair C)
56 {
57 Pair AB = B.subtract(A);
58 Pair BC = C.subtract(B);
59 Pair AC = C.subtract(A);
60
61 int dir = (AB.cross(AC) > 0 ? 1 : -1);
62
63 double low, high, theta;
64 Pair v, u, P;
65 low = 0.0;
66 high = Math.min(angle(B, A, C), angle(A, B, C));
67 high = Math.min(high, angle(A, C, B));
68
69 for(int i = 0; i < 200; ++i)
70 {
71 theta = (low + high) / 2.0;
72 v = AB.rotate(theta * dir);
73 u = BC.rotate(theta * dir);
74 P = intersect(A, v, B, u);
75
76 if(theta > angle(P, C, A)) high = theta;
77 else low = theta;
78 }
79
80 theta = (low + high) / 2.0;
81 v = AB.rotate(theta * dir);
82 u = BC.rotate(theta * dir);
83 return intersect(A, v, B, u);
84 }
85
86
87 public double angle(Pair A, Pair B, Pair C)
88 {
89 Pair BA = A.subtract(B);
90 Pair BC = C.subtract(B);
91 return Math.abs(BA.angle(BC));
92 }
93
94 private class Pair
95 {
96 public double x, y;
97 public Pair(double xx, double yy) { x = xx; y = yy; }
98
99 public double dot(Pair u) { return x*u.x + y*u.y; }
100 public double cross(Pair u) { return x*u.y - u.x*y; }
101 public double angle(Pair u) { return Math.atan2(cross(u), dot(u)); }
102
103 public Pair add(Pair u) { return new Pair(x + u.x, y + u.y); }
104 public Pair subtract(Pair u) { return new Pair(x - u.x, y - u.y); }
105 public Pair multiply(double s) { return new Pair(s * x, s * y); }
106
107 public Pair rotate(double t)
108 {
109 double Tx = x * Math.cos(t) - y * Math.sin(t);
110 double Ty = x * Math.sin(t) + y * Math.cos(t);
111 return new Pair(Tx, Ty);
112 }
113
114 public String toString()
115 {
116 return fmt.format(x + tol) + " " + fmt.format(y + tol);
117 }
118 }
119
120
121 public Pair intersect(Pair a, Pair v, Pair b, Pair u)
122 {
123 double det = (v.x)*(-u.y) - (-u.x)*(v.y);
124 double t = ((-u.y)*(b.x - a.x) + (u.x)*(b.y - a.y)) / det;
125 return a.add(v.multiply(t));
126 }
127
128 public static void main(String[] args) throws Exception
129 {
130 (new YiuEqualAngles()).main();
131 }
132 }
133