The Java Program: D_angles/YiuEqualAngles.java

  1 /*
  2 ACM ICPC Southeast USA Regional Contest 2010
  3 Problem: Equal Angles
  4 
  5 Author: Yiu Yu Ho
  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     //Returns angle ABC
 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     //Intersecting lines a + t(v) and b + s(u)
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