// This file should allow for the drawing of objects in
// hyperbolic geometry using the Klien model of hyperbolic
// geometry

import java.lang.Math;
import java.awt.Graphics;
import java.awt.Color;

class Point {
    //Computation is done in the Klien Model
    double x,y;
    boolean welldefined;
    
    Point (){
	x=0;
	y=0;
	welldefined=true;
    }
    
    Point (double x, double y){
	this.x=x;
	this.y=y;
	welldefined=((x*x+y*y)<1);
    }
    
    Point (Line p1, Line p2){
	this.x=p1.y*p2.z-p1.z*p2.y;
	this.y=p1.z*p2.x-p1.x*p2.z;
	double z=p1.x*p2.y-p1.y*p2.x;
	try { 
	    this.x=this.x/z;
	    this.y=this.y/z;
	} catch (ArithmeticException e) {
	    // This will never happen unless z=0
	    x=1;
	    y=1;
	}
	this.welldefined=(this.x*this.x+this.y*this.y<1);
    }

    Point (Point p){
	this.x=p.x;
	this.y=p.y;
	this.welldefined=p.welldefined;
    }
    
    Point (PointProj p){
	if (p.z!=0){
	    this.x=p.x/p.z;
	    this.y=p.y/p.z;
	}
	welldefined=((x*x+y*y)<1);
    }

    void relocate(double x, double y){
	this.x=x;
	this.y=y;
	welldefined=((x*x+y*y)<1);
    }

    void relocate(Point p){
	this.x=p.x;
	this.y=p.y;
	this.welldefined=p.welldefined;
    }
}

class Line {
    double x,y,z;
    boolean welldefined;
  
    Line (){ //x-axis
	x=0;
	y=1;
	z=0;
	welldefined=true;
    }

    Line (double x, double y, double z){
	double ratio;
	try { ratio=1/Math.sqrt(x*x+y*y+z*z);
    } catch (ArithmeticException e) {
	// This will never happen
	ratio=1;
    }
	this.x=ratio*x;
	this.y=ratio*y;
	this.z=ratio*z;
	welldefined=(x*x+y*y>z*z);
    }

    Line (LineProj l){
	double ratio;
	try { ratio=1/Math.sqrt(l.x*l.x+l.y*l.y+l.z*l.z);
    } catch (ArithmeticException e) {
	// This will never happen
	ratio=1;
    }
	this.x=ratio*l.x;
	this.y=ratio*l.y;
	this.z=ratio*l.z;
	welldefined=(x*x+y*y>z*z);
    }

    Line(Point p1, Point p2){
	Line L=new Line(p1.y-p2.y,
			p2.x-p1.x,
			p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
	welldefined=(x*x+y*y>z*z);  // Always well defined if p1 & p2 are
    }
    
    Line(BoundaryPoint p1, BoundaryPoint p2){
	Line L=new Line(p1.y-p2.y,
			p2.x-p1.x,
			p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
	welldefined=(x*x+y*y>z*z);  // Always well defined if p1 & p2 are
    }
    
    void fix(){
	if (z<0) {
	    this.x=-this.x;
	    this.y=-this.y;
	    this.z=-this.z;
	} else if ((z==0)&&(y<0)) {
	    this.x=-this.x;
	    this.y=-this.y;
	}
    }   

    BoundaryPoint bound1(){
	double x,y;
	try { x=-this.x*this.z-this.y*
		 Math.sqrt(this.x*this.x+this.y*this.y-this.z*this.z);
	      y=-this.y*this.z+this.x*
		 Math.sqrt(this.x*this.x+this.y*this.y-this.z*this.z);
	} catch (ArithmeticException e) {
	    // This will never happen if l welldefined
	    return new BoundaryPoint(0,0);
	}
	return new BoundaryPoint(x,y);
    }

    BoundaryPoint bound2(){
	double x,y;
	try { x=-this.x*this.z+this.y*
		 Math.sqrt(this.x*this.x+this.y*this.y-this.z*this.z);
	      y=-this.y*this.z-this.x*
		 Math.sqrt(this.x*this.x+this.y*this.y-this.z*this.z);
	} catch (ArithmeticException e) {
	    // This will never happen if l welldefined
	    return new BoundaryPoint(0,0);
	}
	return new BoundaryPoint(x,y);
    }
}

class PointProj {
    double x,y,z;
    
    PointProj (){
        x=0;
	y=0;
	z=1;
    }

    PointProj (double x, double y){
	try { this.z=1/Math.sqrt(1+x*x+y*y);
	} catch (ArithmeticException e) {
	    // This will never happen
	}
	this.x=x*this.z;
	this.y=y*this.z;
    }
    
    PointProj (double x, double y, double z){
	double ratio;
	try { ratio=1/Math.sqrt(x*x+y*y+z*z);
	} catch (ArithmeticException e) {
	    // This will never happen
	    ratio=1;
	}
	this.x=ratio*x;
	this.y=ratio*y;
	this.z=ratio*z;
    }
    
    PointProj (LineProj p1, LineProj p2){
	PointProj L=new PointProj(p1.y*p2.z-p1.z*p2.y,
				  p1.z*p2.x-p1.x*p2.z,
				  p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
    }
    
    PointProj (Line p1, Line p2){
	PointProj L=new PointProj(p1.y*p2.z-p1.z*p2.y,
				  p1.z*p2.x-p1.x*p2.z,
				  p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
    }

    PointProj (PointProj p){
	this.x=p.x;
	this.y=p.y;
	this.z=1;
    }

    PointProj (Point p){
	this.x=p.x;
	this.y=p.y;
	this.z=1;
    }

    PointProj (LineProj l){
	this.x=l.x;
	this.y=l.y;
	this.z=l.z;
    }

    PointProj (Line l){
	this.x=l.x;
	this.y=l.y;
	this.z=l.z;
    }

    void fix(){
	if (z<0) {
	    this.x=-this.x;
	    this.y=-this.y;
	    this.z=-this.z;
	} else if ((z==0)&&(y<0)) {
	    this.x=-this.x;
	    this.y=-this.y;
	}
    }

    void relocate(double x, double y){
	try { this.z=1/Math.sqrt(1+x*x+y*y);
	} catch (ArithmeticException e) {
	   // This will never happen
	}
	this.x=x*this.z;
	this.y=y*this.z;
    }

    void relocate(double x, double y, double z){
	double ratio;
	try { ratio=1/Math.sqrt(x*x+y*y+z*z);
	} catch (ArithmeticException e) {
	    ratio=1;  // This will never happen
	}
	this.x=ratio*x;
	this.y=ratio*y;
	this.z=ratio*z;
    }
	
    void relocate(PointProj p){
	this.x=p.x;
	this.y=p.y;
	this.z=p.z;
    }
}

class LineProj {
    double x,y,z;
    
    LineProj (){
	x=0;
	y=0;
	z=1;
    }
    
    LineProj (double x, double y, double z){
	double ratio;
	try { ratio=1/Math.sqrt(x*x+y*y+z*z);
	} catch (ArithmeticException e) {
	    // This will never happen
	    ratio=1;
	}
	this.x=ratio*x;
	this.y=ratio*y;
	this.z=ratio*z;
    }
    
    LineProj (PointProj p1, PointProj p2){
	LineProj L=new LineProj(p1.y*p2.z-p1.z*p2.y,
			    p1.z*p2.x-p1.x*p2.z,
			    p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
    }
    
    LineProj (Point p1, Point p2){
	LineProj L=new LineProj(p1.y-p2.y,
				p2.x-p1.x,
				p1.x*p2.y-p1.y*p2.x);
	this.x=L.x;
	this.y=L.y;
	this.z=L.z;
    }
    
    LineProj (PointProj p){
	this.x=p.x;
	this.y=p.y;
	this.z=p.z;
    }
    
    LineProj (Point p){
	this.x=p.x;
	this.y=p.y;
	this.z=1;
    }

    void fix(){
	if (z<0) {
	    this.x=-this.x;
	    this.y=-this.y;
	    this.z=-this.z;
	} else if ((z==0)&&(y<0)) {
	    this.x=-this.x;
	    this.y=-this.y;
	}
    }
}

class BoundaryPoint{
    double x, y;
    boolean welldefined;
    
    BoundaryPoint (double theta){
	x=Math.cos(theta);
	y=Math.sin(theta);
	welldefined=true;
    }

    BoundaryPoint (BoundaryPoint p){
	this.x=p.x;
	this.y=p.y;
	this.welldefined=p.welldefined;
    }
    
    BoundaryPoint (double x, double y){
	welldefined=true;
	double ratio;
	try { ratio=1/Math.sqrt(x*x+y*y);
	} catch (ArithmeticException e) {
	    // This will never happen unless x=y=0
	    ratio=1;
	    welldefined=false;
	}
	this.x=ratio*x;
	this.y=ratio*y;
    }

    // this returns the line tangent to the unit circle at this point
    LineProj BoundaryLine(){
      return new LineProj(-x,-y,1);
    }

}

class Transform {
    double m11,m12,m21,m22;
    boolean welldefined; // well defined for non-zero determinant

    Transform ( double m11, double m12, double m21, double m22) {
	this.m11=m11;
	this.m12=m12;
	this.m21=m21;
	this.m22=m22;
	welldefined=(m11*m22-m12*m21 != 0);
    }

    Transform ( ) {
	this.m11=1;
	this.m12=0;
	this.m21=0;
	this.m22=1;
	welldefined=true;
    }

    Transform ( double theta ) {  // rotation of angle theta about center
	this.m11=Math.cos(theta/2);
	this.m12=-Math.sin(theta/2);
	this.m21=Math.sin(theta/2);
	this.m22=Math.cos(theta/2);
	welldefined=true;
    }

    Transform ( Transform T ) {  // copy
	this.m11=T.m11;
	this.m12=T.m12;
	this.m21=T.m21;
	this.m22=T.m22;
	this.welldefined=T.welldefined;
    }

    Transform ( Transform S, Transform T ) {  // multiply S & T
	this.m11=S.m11*T.m11+S.m12*T.m21;
	this.m12=S.m11*T.m12+S.m12*T.m22;
	this.m21=S.m21*T.m11+S.m22*T.m21;
	this.m22=S.m21*T.m12+S.m22*T.m22;
	this.welldefined=((S.welldefined)&&(T.welldefined));
    }

    Transform inverse() {  // T^-1
	return new Transform( m22, -m12, -m21, m11);
    }

    Transform expon( int num ) {  // T^i i>=0
	Transform T=new Transform();
	for (int i=0;i<num;i++)
	    T=this.dot(T);
	return T;
    }

    Transform ( double x, double y ) {  // translate center by x, y
	// absolute values of x and y should be less than 1
	// this is an involution

	welldefined=(x*x+y*y<1);
	if (welldefined){
	    try { 
		double z=Math.sqrt(x*x+y*y);
		Transform T=new Transform(-1-Math.sqrt(1-z*z),
					  z,
					  -z,
					  1+Math.sqrt(1-z*z));
		double theta;
		if (x!=0) 
		    theta=Math.atan(y/x);
		else if (y>0) // x=0
		    theta=Math.PI/2;
		else if (y<0)
		    theta=-Math.PI/2;
		else { // y=0
		    this.m11=1;
		    this.m12=0;
		    this.m21=0;
		    this.m22=1;
		    welldefined=true;
		    return;
		}
		if (x<0)
		    theta=theta+Math.PI;
		Transform R=new Transform(theta);
		Transform R2=new Transform(-theta);
		Transform S=new Transform(R2.dot(T.dot(R)));
		this.m11=S.m11;
		this.m12=S.m12;
		this.m21=S.m21;
		this.m22=S.m22;
		this.welldefined=S.welldefined;
	    } catch (ArithmeticException e) {
		// This will never happen
	    }
	}
    }

    Transform dot(Transform T){
	return new Transform(this,T);
    }

    PointProj dot(PointProj P){
	// this looks weird but is the key to this entire class
        return new PointProj( (m12*m21+m11*m22)*P.x+
			      (m11*m21-m12*m22)*P.y+
			      (m11*m21+m12*m22)*P.z,
			      (m11*m12-m21*m22)*P.x+
			      (m11*m11-m12*m12-m21*m21+m22*m22)/2*P.y+
			      (m11*m11+m12*m12-m21*m21-m22*m22)/2*P.z,
			      (m11*m12+m21*m22)*P.x+
			      (m11*m11-m12*m12+m21*m21-m22*m22)/2*P.y+
			      (m11*m11+m12*m12+m21*m21+m22*m22)/2*P.z );
    }

    Point dot(Point P){
	PointProj Q=this.dot(new PointProj(P.x,P.y,1));
	if (Q.z != 0)
	    return new Point(Q.x/Q.z, Q.y/Q.z);
	return new Point(1,1);
    }

    BoundaryPoint dot(BoundaryPoint P){
	PointProj Q=this.dot(new PointProj(P.x,P.y,1));
	if (Q.z != 0)
	    return new BoundaryPoint(Q.x/Q.z, Q.y/Q.z);
	return new BoundaryPoint(0,0);
    }

    Line dot(Line L){
	if (L.welldefined)
	    return new Line( this.dot(L.bound1()),
			     this.dot(L.bound2()) );
	return new Line(0,0,1);
    }

}

class Screen {
    int rad,transX,transY;
    int model;        
    // model=0 => Klien model
    // model=1 => Poincare Disk model

    Screen ( int rad, int transX, int transY){
	this.rad=rad;
	this.transX=transX;
	this.transY=transY;
	model=1; //Plot with Klien Model
    }

    void KlienModel(){
	model=1;
    }

    void PoincareModel(){
	model=0;
    }
    
    void clear(Graphics g){
	g.setColor(Color.white);
	g.fillOval(transX,transY,2*rad,2*rad);
	g.setColor(Color.lightGray);
	g.drawOval(transX,transY,2*rad,2*rad);
    }

    void plotPoint(Graphics g, Point p){
	if (p.welldefined){
	    if (model==0){  // Poincare
		if ((p.x==0)&&(p.y==0)){
		    g.drawRect( transX+(int)( rad ) -2,
				transY+(int)( rad ) -2, 
				5, 5);
		} else {
		    try {
 			double ratio=(1-Math.sqrt(1-p.x*p.x-p.y*p.y))/
			    (p.x*p.x+p.y*p.y);
			g.drawRect( transX+(int)( rad*(p.x*ratio+1) ) -2,
				    transY+
				    (int)( 2*rad - rad*(p.y*ratio+1) ) -2, 
				    5, 5);
		    } catch (ArithmeticException e) {
			// This will never happen unless x=y=0
			g.drawRect( transX+(int)( rad ) -2,
				    transY+(int)( rad ) -2, 
				    5, 5);
		    }
		}
	    } else if (model==1) { // Klien
		g.drawRect( transX+(int)( rad*(p.x+1) ) -2,
			    transY+(int)( 2*rad - rad*(p.y+1) ) -2, 5, 5);
	    }
	}
    }

    void plotPoint(Graphics g, BoundaryPoint p){
	if (p.welldefined){
	    if (model==0){  // Poincare
		g.drawRect( transX+(int)( rad*(p.x+1) ) -2,
			    transY+(int)( 2*rad - rad*(p.y+1) ) -2, 5, 5);
	    } else if (model==1) { // Klien
		g.drawRect( transX+(int)( rad*(p.x+1) ) -2,
			    transY+(int)( 2*rad - rad*(p.y+1) ) -2, 5, 5);
	    }
	}
    }
    
    void drawPoint(Graphics g, Point p){
	if (p.welldefined){
	    if (model==0){  // Poincare
		if ((p.x==0)&&(p.y==0)){
		    g.drawLine( transX+(int)( rad ),
				transY+(int)( rad ),
				transX+(int)( rad ),
				transY+(int)( rad ));
		} else {
		    try {
			double ratio=(1-Math.sqrt
				      (1-p.x*p.x-p.y*p.y))/(p.x*p.x+p.y*p.y);
			g.drawLine( transX+(int)( rad*(p.x*ratio+1) ),
				    transY+(int)( 2*rad - rad*(p.y*ratio+1) ),
				    transX+(int)( rad*(p.x*ratio+1) ),
				    transY+(int)( 2*rad - rad*(p.y*ratio+1) ));
		    } catch (ArithmeticException e) {
			// This will never happen unless x=y=0
			g.drawLine( transX+(int)( rad ),
				    transY+(int)( rad ),
				    transX+(int)( rad ),
				    transY+(int)( rad ));
		    }
		}
	    } else if (model==1) { // Klien
		g.drawLine( transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ),
			    transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ));
	    }
	}
    }

    void drawPoint(Graphics g, BoundaryPoint p){
	if (p.welldefined){
	    if (model==0){  // Poincare
		g.drawLine( transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ),
			    transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ));
	    } else if (model==1) { // Klien
		g.drawLine( transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ),
			    transX+(int)( rad*(p.x+1) ),
			    transY+(int)( 2*rad - rad*(p.y+1) ));
	    }
	}
    }
    
    boolean isPoint(Point p, int x, int y){
	if ((p.welldefined)&&((x-transX)*(x-transX)+
			      (y-transY)*(y-transY)<rad*rad)) {
	    if (model==0){ // Poincare
		double ratiop;
		try { ratiop=(1-Math.sqrt(1-p.x*p.x-p.y*p.y))
			  /(p.x*p.x+p.y*p.y);
		} catch (ArithmeticException e) {
		    // This will never happen unless x=y=0
		    ratiop=1;
		}
		return ((transX+(int)(rad*(p.x*ratiop+1))-x<3)&&
			(transX+(int)(rad*(p.x*ratiop+1))-x>-3)&&
			(transY+(int)(2*rad-rad*(p.y*ratiop+1))-y<3)&&
		        (transY+(int)(2*rad-rad*(p.y*ratiop+1))-y>-3));
	    }
	    if (model==1){ // Klien
		return ((transX+(int)( rad*(p.x+1) )-x<3)&&
			(transX+(int)( rad*(p.x+1) )-x>-3)&&
			(transY+(int)( 2*rad - rad*(p.y+1) )-y<3)&&
			(transY+(int)( 2*rad - rad*(p.y+1) )-y>-3));
	    }
	}
	return false;
    }
    
    void drawLineSegment(Graphics g, Point p, Point q){
	if ((p.welldefined)&&(q.welldefined)){
	    if (model==0) { // Poincare
		int px,py,qx,qy;
		if ((p.x==0)&&(p.y==0)){
		    px=transX+rad;
		    py=transY+rad;
		} else {
		    try {
			double ratio=(1-Math.sqrt
				      (1-p.x*p.x-p.y*p.y))/(p.x*p.x+p.y*p.y);
			px=transX+(int)( rad*(p.x*ratio+1) );
			py=transY+(int)( 2*rad - rad*(p.y*ratio+1) );
		    } catch (ArithmeticException e) {
			// This will never happen unless x=y=0
			px=transX+rad;
			py=transY+rad;
		    }
		}
		if ((q.x==0)&&(q.y==0)){
		    qx=transX+rad;
		    qy=transY+rad;
		} else {
		    try {
			double ratio=(1-Math.sqrt
				      (1-q.x*q.x-q.y*q.y))/(q.x*q.x+q.y*q.y);
			qx=transX+(int)( rad*(q.x*ratio+1) );
			qy=transY+(int)( 2*rad - rad*(q.y*ratio+1) );
		    } catch (ArithmeticException e) {
			// This will never happen unless x=y=0
			qx=transX+rad;
			qy=transY+rad;
		    }
		}
		Line l= new Line(p,q);
		if (l.z==0) { // goes through origin
		    g.drawLine(px,py,qx,qy);
		} else {
		    PointProj O=new PointProj(l.bound1().BoundaryLine(),
					      l.bound2().BoundaryLine());
		    // O is center
		    int ox,oy;
		    int rad2;
		    try {
			ox=transX+(int)( rad*(O.x/O.z+1) );
			oy=transY+(int)( 2*rad - rad*(O.y/O.z+1) );
			rad2=(int) ( Math.sqrt((ox-px)*(ox-px)+
					       (oy-py)*(oy-py)) );
			double theta1,theta2;
			theta1=Math.atan2(px-ox, py-oy);
			theta2=Math.atan2(qx-ox, qy-oy)-theta1;
			if (theta2<-Math.PI)
			    theta2=theta2+2*Math.PI;
			else if (theta2>Math.PI)
			    theta2=theta2-2*Math.PI;
			g.drawArc(ox-rad2,oy-rad2,2*rad2,2*rad2,
				  (int)(270+180*theta1/Math.PI),
				  (int)( theta2*180/Math.PI));
		    } catch (ArithmeticException e) {
			// This will never happen
		    }
		}
	    } else if (model==1){ // Klien
		g.drawLine(transX+(int)( rad*(p.x+1) ),
			   transY+(int)( 2*rad - rad*(p.y+1) ),
			   transX+(int)( rad*(q.x+1) ),
			   transY+(int)( 2*rad - rad*(q.y+1) ));
	    }
	}
    }

    void drawLine(Graphics g, BoundaryPoint p, BoundaryPoint q){
	if ((p.welldefined)&&(q.welldefined)){
	    if (model==0) { // Poincare
	    } else if (model==1){ // Klien
		g.drawLine(transX+(int)( rad*(p.x+1) ),
			   transY+(int)( 2*rad - rad*(p.y+1) ),
			   transX+(int)( rad*(q.x+1) ),
			   transY+(int)( 2*rad - rad*(q.y+1) ));
	    }
	}
    }

    void drawLine(Graphics g, Line l){
	if (l.welldefined)
	    drawLine(g, l.bound1(), l.bound2());
    }

    void drawLine(Graphics g, LineProj l){
	drawLine(g, new Line(l));
    }

    void movePoint(Point p, int x, int y){
	if ((x-transX)*(x-transX)+(y-transY)*(y-transY)<rad*rad) {
	    if (model==0) { //Poincare
		double ratio=2/(1+x*x+y*y);
		p.relocate( (x-transX-rad)*ratio/rad,
			    (y-transY-rad)*ratio/rad );
	    } else if (model==1) { //Klien
		p.relocate( (x-transX-rad)/rad,
			    (y-transY-rad)/rad ); 
	    }
	}
    }
}