SHapes

import java.util.*;

abstract class Shape{
    public abstract Point center();
    public abstract double perimeter();
    public abstract double area();
    public abstract void translate(final Point newCenter);
    public abstract void rotate(final double angle);
    public abstract void scale(final double coefficient);
}
class Point{
    double x,y;

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

    public Point add(double x,double y){
        return new Point(this.x+x,this.y+y);
    }
    public Point subtract(double x,double y){
        return new Point(this.x-x,this.y-y);
    }
    public Point multiply(double factor){
        return new Point(this.x*factor,this.y*factor);
    }
    public Point divide(double factor){
        return new Point(this.x/factor,this.y/factor);
    }
    public Point rotate(Point p, double angle){
        double sin = Math.sin(angle);
        double cos = Math.cos(angle);
        double rotatedX = p.x + (x-p.x)*cos-(y-p.y)*sin;
        double rotatedY = p.y + (x-p.x)*sin+(y-p.y)*cos;
        return new Point(rotatedX,rotatedY);
    }
    public double x(){
        return x;
    }
    public double y(){
        return y;
    }
    public Point midpoint(Point p){
        return new Point((p.x+x)/2,(p.y+y)/2);
    }
    public static double distance(Point p,Point p1){
        return Math.sqrt((p.x-p1.x)*(p.x-p1.x)+(p.y-p1.y)*(p.y-p1.y));
    }
}
class Ellipse extends Shape{
    Point p1,p2;
    double perifocus;
    public Ellipse(Point p1,Point p2,double perifocus) {
        this.p1 = p1;
        this.p2 = p2;
        this.perifocus = perifocus;
    }
    public List<Point> focuses(){
        List<Point> l = new ArrayList<>();
        l.add(p1);
        l.add(p2);
        return l;
    }

    public double focalDistance(){
        return Point.distance(p1,p2)/2;
    }

    public double majorSemiAxis(){
        return Point.distance(p1,this.center())+perifocus;
    }

    public double minorSemiAxis(){
        double maxx = Math.max(Math.pow(this.majorSemiAxis(),2),Math.pow(Point.distance(p1,this.center()),2));
        double minn =  Math.min(Math.pow(this.majorSemiAxis(),2),Math.pow(Point.distance(p1,this.center()),2));
        return Math.sqrt(maxx-minn);
    }

    public double eccentricity(){
        return Point.distance(p1,this.center())/this.majorSemiAxis();
    }
    @Override
    public Point center() {
        return p1.midpoint(p2);
    }

    @Override
    public double perimeter() {
        double a = this.majorSemiAxis();
        double b = this.minorSemiAxis();
        return (4*((Math.PI*a*b+(a-b)*(a-b))/(a+b)));
    }

    @Override
    public double area() {
        double a = this.majorSemiAxis();
        double b = this.minorSemiAxis();
        return Math.PI*a*b;
    }

    @Override
    public void translate(Point newCenter) {
        Point currentCenter = center();
        double dX = newCenter.x-currentCenter.x;
        double dY = newCenter.y-currentCenter.y;
        p1 = p1.add(dX,dY);
        p2 = p2.add(dX,dY);
    }

    @Override
    public void rotate(double angle) {
        Point center = center();
        p1 = p1.rotate(center,angle);
        p2 = p2.rotate(center,angle);
    }

    @Override
    public void scale(double coefficient) {
        perifocus=Math.abs(perifocus*coefficient);
        Point center = center();
        double dx1 = p1.x - center.x;
        double dy1 = p1.y - center.y;
        double dx2 = p2.x - center.x;
        double dy2 = p2.y - center.y;
        p1 = new Point(center.x + dx1 * coefficient, center.y + dy1 * coefficient);
        p2 = new Point(center.x + dx2 * coefficient, center.y + dy2 * coefficient);
    }
}
class Circle extends Ellipse{
    Point p;
    double perifocus;
    public Circle(Point p, double perifocus) {
        super(p, p, perifocus);
        this.p = p;
        this.perifocus  = perifocus;
    }
    public double radius(){
        return minorSemiAxis();
    }
}
class Rectangle extends Shape{
    Point p1,p2;
    double height;
    public Rectangle(Point p1, Point p2, double height){
        this.p1 = p1;
        this.p2 = p2;
        this.height = height;
    }
    public List<Point> vertices() {
        Point center = center();
        double angle = Math.atan2(Math.abs(center.y-p1.y),Math.abs(center.x-p1.x));
        List<Point> vertices = new ArrayList<>();
        double halfWidth = firstSide() / 2.0;
        double halfHeight = secondSide() / 2.0;
        double sin = Math.sin(angle);
        double cos = Math.cos(angle);
        Point vertex1 = new Point(center.x + cos * (-halfWidth) - sin * (-halfHeight),
                center.y+ sin * (-halfWidth) + cos * (-halfHeight));
        Point vertex2 = new Point(center.x + cos * (halfWidth) - sin * (-halfHeight),
                center.y + sin * (halfWidth) + cos * (-halfHeight));
        Point vertex3 = new Point(center.x + cos * (halfWidth) - sin * (halfHeight),
                center.y + sin * (halfWidth) + cos * (halfHeight));
        Point vertex4 = new Point(center.x + cos * (-halfWidth) - sin * (halfHeight),
                center.y + sin * (-halfWidth) + cos * (halfHeight));
        vertices.add(vertex1);
        vertices.add(vertex2);
        vertices.add(vertex3);
        vertices.add(vertex4);
        vertices.sort((pA, pB) -> {
            double angle1 = Math.atan2(pA.y - center.y, pA.x - center.x);
            double angle2 = Math.atan2(pB.y - center.y, pB.x - center.x);
            if (angle1 < 0) {
                angle1 += 2 * Math.PI;
            }
            if (angle2 < 0) {
                angle2 += 2 * Math.PI;
            }
            return Double.compare(angle1, angle2);
        });
        List<Double> l = new ArrayList<>();
        double ang = Math.atan2(p1.y-center.y,p1.x-center.x);
        if (ang < 0) {
            ang += 2 * Math.PI;
        }
        for (Point i : vertices){
            double an = Math.atan2(i.y-center.y,i.x-center.x);
            if (an < 0) {
                an += 2 * Math.PI;
            }
            l.add(an);
        }

        if (ang > l.get(3)){
            return vertices;
        }
        else{
            int pointer = 0;
            for (int i = 0;i<3;++i){
                if (ang<l.get(i)){
                    pointer = i;
                    break;
                }
            }
            List<Point> p = new ArrayList<>();
            for (int i = pointer;i<l.size();++i){
                p.add(vertices.get(i));
            }
            for (int i = 0;i<pointer;++i){
                p.add(vertices.get(i));
            }
            return p;
        }
    }


    public double firstSide(){
        return Point.distance(p1,p2);
    }
    public double secondSide(){
        return height;
    }
    public double diagonal(){
        return Math.sqrt(firstSide()*firstSide()+secondSide()*secondSide());
    }

    @Override
    public Point center() {
        return p1.midpoint(p2);
    }

    @Override
    public double perimeter() {
        return (firstSide()+secondSide())*2;
    }

    @Override
    public double area() {
        return firstSide()*secondSide();
    }

    @Override
    public void translate(Point newCenter) {
        Point currentCenter = center();
        double dX = newCenter.x-currentCenter.x;
        double dY = newCenter.y-currentCenter.y;
        p1 = p1.add(dX,dY);
        p2 = p2.add(dX,dY);
    }

    @Override
    public void rotate(double angle) {
        Point center = center();
        p1 = p1.rotate(center,angle);
        p2 = p2.rotate(center,angle);
    }

    @Override
    public void scale(double coefficient) {
        height=Math.abs(height*coefficient);
        Point center = center();
        double dx1 = p1.x - center.x;
        double dy1 = p1.y - center.y;
        double dx2 = p2.x - center.x;
        double dy2 = p2.y - center.y;
        p1 = new Point(center.x + dx1 * coefficient, center.y + dy1 * coefficient);
        p2 = new Point(center.x + dx2 * coefficient, center.y + dy2 * coefficient);
    }
}
class Square extends Rectangle{
    Point p1,p2;
    public Square(Point p1, Point p2) {
        super(p1, p2, Point.distance(p1,p2));
    }
    public double side(){
        return firstSide();
    }
    public Circle circumscribedCircle(){
        return new Circle(center(),diagonal()/2);
    }
    public Circle inscribedCircle(){
        return new Circle(center(),side()/2);
    }
}
class Triangle extends Shape{
    Point p1,p2,p3;
    public Triangle(Point p1, Point p2, Point p3){
        this.p1 = p1;
        this.p2 = p2;
        this.p3 = p3;
    }

    public List<Point> vertices(){
        List<Point> l = new ArrayList<>();
        l.add(p1);
        l.add(p2);
        l.add(p3);
        return l;
    }

    public Circle circumscribedCircle(){
        double r = (Point.distance(p1,p2)*Point.distance(p3,p2)*Point.distance(p1,p3))/(4*area());
        double xC = (-0.5)*(p1.y*(p2.x*p2.x+p2.y*p2.y-p3.x*p3.x-p3.y*p3.y)+p2.y*(p3.x*p3.x+p3.y*p3.y-p1.x*p1.x-p1.y*p1.y)+p3.y*(p1.x*p1.x+p1.y*p1.y-p2.x*p2.x-p2.y*p2.y))/(p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y));
        double yC = (0.5)*(p1.x*(p2.x*p2.x+p2.y*p2.y-p3.x*p3.x-p3.y*p3.y)+p2.x*(p3.x*p3.x+p3.y*p3.y-p1.x*p1.x-p1.y*p1.y)+p3.x*(p1.x*p1.x+p1.y*p1.y-p2.x*p2.x-p2.y*p2.y))/(p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y));
        return new Circle(new Point(xC,yC),r);
    }
    public Circle inscribedCircle(){
        double r = 2*area()/perimeter();
        double xC = ((p1.x + p2.x - 2*p3.x)*((p3.y - p1.y)*(p2.x + p3.x - 2*p1.x) + p1.x*(p2.y + p3.y - 2*p1.y)) - p3.x*(p2.x + p3.x - 2*p1.x)*(p1.y + p2.y - 2*p3.y))/((p2.y + p3.y - 2*p1.y)*(p1.x + p2.x - 2*p3.x) - (p2.x + p3.x - 2*p1.x)*(p1.y + p2.y - 2*p3.y));
        double yC = ((xC - p1.x)*(p2.y + p3.y - 2*p1.y)/(p2.x + p3.x - 2*p1.x)) + p1.y;
        return new Circle(new Point(xC,yC),r);
    }
    public Point orthocenter(){
        double Ax = p3.x - p2.x;
        double Bx = p3.y - p2.y;
        double Cx = p1.x * (p3.x - p2.x) + p1.y * (p3.y - p2.y);
        double Ay = p3.x - p1.x;
        double By = p3.y - p1.y;
        double Cy = p2.x * (p3.x - p1.x) + p2.y * (p3.y - p1.y);
        double det = Ax * By - Ay * Bx;
        double detX = Cx * By - Cy * Bx;
        double detY = Ax * Cy - Ay * Cx;
        return new Point(detX/det,detY/det);
    }
    public Circle ninePointsCircle(){
        Circle c = circumscribedCircle();
        Point p = orthocenter().midpoint(c.center());
        double r = c.radius()/2;
        return new Circle(p,r);
    }

    @Override
    public Point center() {
        return new Point((p1.x+p2.x+p3.x)/3,(p1.y+p2.y+p3.y)/3);
    }

    @Override
    public double perimeter() {
        return Point.distance(p1,p2)+Point.distance(p1,p3)+Point.distance(p2,p3);
    }

    @Override
    public double area() {
        return 0.5*(p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y));
    }

    @Override
    public void translate(Point newCenter) {
        Point currentCenter = center();
        double dX = newCenter.x-currentCenter.x;
        double dY = newCenter.y-currentCenter.y;
        p1.add(dX,dY);
        p2.add(dX,dY);
        p3.add(dX,dY);
    }

    @Override
    public void rotate(double angle) {
        Point center = center();
        p1 = p1.rotate(center,angle);
        p2 = p2.rotate(center,angle);
        p3 = p3.rotate(center,angle);
    }

    @Override
    public void scale(double coefficient) {
        Point center = center();
        double dX = p1.x-center.x;
        double dY = p1.y-center.y;
        p1 = p1.add(dX*coefficient,dY*coefficient);
        dX = p2.x-center.x;
        dY = p2.y-center.y;
        p2 = p2.add(dX*coefficient,dY*coefficient);
        dX = p3.x-center.x;
        dY = p3.y-center.y;
        p3 = p3.add(dX*coefficient,dY*coefficient);
    }
}