/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Capsule
{
  Point2D c1, c2;
  double r;

  public Capsule(Point2D c1, Point2D c2, double r)
  {
    this.c1 = c1;
    this.c2 = c2;
    this.r = r;
  }

  public Point2D[] intersect(Point2D r1, Point2D r2)
  {        
    Point2D cv = Point2D.diff(c2, c1);
    Point2D cu = cv.unit();
    if(cu == null) return null;
    Point2D ncu = cu.norm();
    
    Point2D p1 = Point2D.addTimes(c1, ncu, r);
    Point2D p2 = Point2D.addTimes(c2, ncu, r);
    Point2D p3 = Point2D.addTimes(c1, ncu, -r);
    Point2D p4 = Point2D.addTimes(c2, ncu, -r);
    
    double[] wh = new double[6];
    wh[0] = Point2D.raySeg(r1, r2, p1, p2);
    wh[1] = Point2D.raySeg(r1, r2, p3, p4);
    Point2D.rayCircle(r1, r2, c1, r, wh, 2);
    Point2D.rayCircle(r1, r2, c2, r, wh, 4);
    
    double hMin = Double.POSITIVE_INFINITY;
    double hMax = Double.NEGATIVE_INFINITY;
    for(double h : wh)
    {
      if(!Double.isNaN(h))
      {
        hMin = Math.min(h, hMin);
        hMax = Math.max(h, hMax);
      }
    }
        
    Point2D rd = Point2D.diff(r2, r1);
    Point2D iMin = Point2D.addTimes(r1, rd, hMin);
    if(hMin == hMax) return new Point2D[]{iMin};
    Point2D iMax = Point2D.addTimes(r1, rd, hMax);    
    return new Point2D[]{iMin, iMax};
  }
  
  static class Point2D 
  {
    double x;
    double y;
    
    public Point2D(double x, double y)
    {
      this.x = x;
      this.y = y;
    }

    // https://stackoverflow.com/a/1084899/6438819
    public static void rayCircle(Point2D p, Point2D pe, Point2D cc, double r, double[] res, int off)
    {
      Point2D d = Point2D.diff(p, pe);
      Point2D f = Point2D.diff(cc, p);
      
      double a = d.lengthSq();
      double b = 2*Point2D.dot(f, d);
      double c = f.lengthSq() - r*r;
      
      double disc = b*b-4*a*c;
      if(disc < 0)
      {
        res[off] = res[off+1] = Double.NaN;
        return;
      }      
      double discRoot = Math.sqrt(disc);      
      res[off] = (-b - discRoot)/(2*a);
      res[off+1] = (-b + discRoot)/(2*a);
    }
    
    // https://stackoverflow.com/a/565282/6438819
    public static double raySeg(Point2D p, Point2D pe, Point2D q, Point2D qe)
    {
      Point2D r = Point2D.diff(pe, p);
      Point2D s = Point2D.diff(qe, q);
      
      double sr = Point2D.cross(s, r);
      if(sr == 0) return Double.NaN;

      Point2D pq = Point2D.diff(p, q);
      double pqr = Point2D.cross(pq, r);
      
      double u = pqr /sr;
      if(u<0 || u>1) return Double.NaN; 
              
      Point2D qp = Point2D.diff(q, p);
      double rs = Point2D.cross(r, s);
      double qps = Point2D.cross(qp, s);
      return qps / rs;
    }

    private static double dot(Point2D p1, Point2D p2)
    {
      return p1.x*p2.x + p1.y*p2.y;
    }

    private static double cross(Point2D p1, Point2D p2)
    {
      return p1.x*p2.y - p1.y*p2.x;
    }

    public static Point2D addTimes(Point2D c, Point2D u, double r)
    {
      return new Point2D(c.x + u.x*r, c.y + u.y*r);
    }

    // CCW
    public Point2D norm()
    {
      return new Point2D(-y, x);
    }

    public Point2D unit()
    {
      double d = length();
      if(d == 0) return null;
      return new Point2D(x/d, y/d);
    }

    public double length()
    {
      return Math.sqrt(lengthSq());
    }
    
    public double lengthSq()
    {
      return x*x+y*y;
    }
    
    public static Point2D diff(Point2D r2, Point2D r1)
    {
      return new Point2D(r2.x-r1.x, r2.y-r1.y);
    }
    
    public String toString()
    {
      return String.format("(%f, %f)", x, y);
    }

    public static double dist(double x2, double y2, int x3, int y3)
    {
      return Math.sqrt((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2));
    }

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

  public static void main(String[] args)
  {
    Capsule cap = new Capsule(new Point2D(0, 0), new Point2D(2, 0), 0.5);
    Point2D[] h = cap.intersect(new Point2D(1, -1), new Point2D(1, 1));
    System.out.println(Arrays.toString(h));
  }
}