Problem: Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Input

The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

Output

Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

Examples

Input

0.000000 0.000000
1.000000 1.000000
0.000000 1.000000


Output

1.00000000

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Solution {
  private static final double MIN_REMAINDER_LIMIT
      = 2.0 * Math.PI / 100.5;

  private static double     s_dMinArea;
  private static double     s_dRadius;
  private static double[]   s_dAbsoluteAngles = new double[3];
  private static double[]   s_dOrigin = new double[2];
  private static double[]   s_dSegmentWidths = new double[3];
  private static double[][] s_dCoordinates = new double[3][2];
  private static int        s_nPoleCount;

  public static void main(String[] args) {
    process(System.in,
            System.out);
  }

  public static void process(InputStream is,
                             PrintStream ps) {
    Scanner scanner;

    scanner = new Scanner(is);

    for (int i = 0; i < 3; i++) {
      s_dCoordinates[i][0] = scanner.nextDouble();
      s_dCoordinates[i][1] = scanner.nextDouble();
    }

    process(s_dCoordinates,
            ps);
//try { Thread.sleep(10000); } catch (Exception e) {}
  }

  public static void debug() {
    System.out.println("Solution:");

    System.out.println("             Area: " + s_dMinArea);
    System.out.println("           Origin: ("
                       + s_dOrigin[0]
                       + ","
                       + s_dOrigin[1]
                       + ")");
    System.out.println("           Radius: " + s_dRadius);
    System.out.println("       Pole count: " + s_nPoleCount);
    System.out.print(  "  Absolute angles: ");
    for (int i = 0; i < s_dAbsoluteAngles.length; i++) {
      if (0 != i) {
        System.out.print("                   ");
      }

      System.out.println(s_dAbsoluteAngles[i] * 180.0 / Math.PI);
    }
    System.out.print("   Segment widths: ");
    for (int i = 0; i < s_dSegmentWidths.length; i++) {
      if (0 != i) {
        System.out.print("                   ");
      }

      System.out.println(s_dSegmentWidths[i] * 180.0 / Math.PI);
    }
    System.out.print(  "      Coordinates: ");

    for (int i = 0; i < s_dCoordinates.length; i++) {
      if (i > 0) {
        System.out.print("                   ");
      }

      System.out.println("("
                         + s_dCoordinates[i][0]
                         + ","
                         + s_dCoordinates[i][1]
                         + ")");
    }
  }

  public static int getPoleCount() {
    return s_nPoleCount;
  }

  private static void process(double[][]  dCoordinates,
                              PrintStream ps) {
    double     dBeta;
    double     dTemp;
    double[]   dTotals = new double[2];
    double[][] dIntersections = new double[3][2];
    Line[]     lines = new Line[3];

    for (int i = 0; i < 3; i++) {
      lines[i] = Line.bisectPoints(dCoordinates[i][0],
                                   dCoordinates[i][1],
                                   dCoordinates[(i + 1) % 3][0],
                                   dCoordinates[(i + 1) % 3][1]);
    }

    for (int i = 0; i < 3; i++) {
      lines[i].intersect(lines[(i + 1) % 3],
                         dIntersections[i]);

      dTotals[0] += dIntersections[i][0];
      dTotals[1] += dIntersections[i][1];
    }

    s_dOrigin[0] = dTotals[0] / 3.0;
    s_dOrigin[1] = dTotals[1] / 3.0;

    dTotals[0] = 0.0;
    for (int i = 0; i < 3; i ++) {
      dTotals[0] += Math.sqrt(  Math.pow(dCoordinates[i][0] - s_dOrigin[0],
                 +                       2.0)
                 +            + Math.pow(dCoordinates[i][1] - s_dOrigin[1],
                 +                       2.0));
    }

    s_dRadius = dTotals[0] / 3.0;

    for (int i = 0; i < 3; i++) {
      s_dAbsoluteAngles[i] = Math.atan2(dCoordinates[i][1] - s_dOrigin[1],
                                        dCoordinates[i][0] - s_dOrigin[0]);
    }

    for (int i = 2; i >= 1; i--) {
      for (int j = 0; j < i; j++) {
        if (s_dAbsoluteAngles[j] > s_dAbsoluteAngles[j + 1]) {
          dTemp = s_dAbsoluteAngles[j];
          s_dAbsoluteAngles[j] = s_dAbsoluteAngles[j + 1];
          s_dAbsoluteAngles[j + 1] = dTemp;
        }
      }
    }

    s_dSegmentWidths[0] = s_dAbsoluteAngles[1] - s_dAbsoluteAngles[0];
    s_dSegmentWidths[1] = s_dAbsoluteAngles[2] - s_dAbsoluteAngles[1];
    s_dSegmentWidths[2] = s_dAbsoluteAngles[0] - s_dAbsoluteAngles[2]
                          + 2.0 * Math.PI;

//    s_nPoleCount = processSegmentWidths(s_dSegmentWidths);
    s_nPoleCount = processSegmentWidths2(s_dSegmentWidths);

    dBeta = 2.0 * Math.PI / s_nPoleCount / 2.0;

    s_dMinArea = s_nPoleCount
                 * s_dRadius * s_dRadius
                 * Math.cos(dBeta) * Math.sin(dBeta);
    ps.println(String.format("%8.6f", s_dMinArea));
  }

  private static int processSegmentWidths(double[] dSegmentWidths) {
    double   dMinRemainder;
    double   dLatestMinRemainder = Double.MAX_VALUE;
    double[] dRemainders;
    int      nMinPoleCount;

    dRemainders = Arrays.copyOf(dSegmentWidths,
                                dSegmentWidths.length);

//    while (!bDone) {
    while (true) {
      dMinRemainder = Double.MAX_VALUE;

System.out.print("Checking for min remainder out of");
      for (double dValue : dRemainders) {
System.out.print(" " + dValue * 180.0 / Math.PI);
        if (0.0 != dValue
            && dValue < dMinRemainder) {
          dMinRemainder = dValue;
        }
      }
System.out.println();

      if (Double.MAX_VALUE == dMinRemainder) {
System.out.println("Breaking because no min value found");
        break;
      } else {
        dLatestMinRemainder = dMinRemainder;
      }

System.out.println("Min value found was " + dMinRemainder * 180.0 / Math.PI);
      for (int i = 0; i < dSegmentWidths.length; i++) {
        dRemainders[i] = dSegmentWidths[i] % dMinRemainder;

        if (   dRemainders[i] < MIN_REMAINDER_LIMIT
            && 0.0 != dRemainders[i]) {
System.out.println("Discarding remainder which is 1 part in " + ((int) Math.round(2.0 * Math.PI / dRemainders[i])) + " of a full circle");
          dRemainders[i] = 0.0;
        }
      }
    }

System.out.println("Min remainder is " + dMinRemainder);

    nMinPoleCount = (int) Math.round(2.0 * Math.PI / dLatestMinRemainder);

System.out.println("Pole count: " + nMinPoleCount);
if (nMinPoleCount > 100) {
 System.out.println("WHAT");
 try { Thread.sleep(5000); } catch (Exception e) {}
}
    return nMinPoleCount;
  }

  private static void showAngles(String      sTitle,
                                 double[]    dAngles,
                                 PrintStream ps) {
    ps.print(sTitle + ": ");
    for (int i = 0; i < dAngles.length; i++) {
      ps.print((float) (dAngles[i] * 180.0 / Math.PI) + " ");
    }
    ps.println();
  }

  private static int processSegmentWidths2(double[] dSegmentWidths) {
    final int[] DENOMINATORS = new int[] { 0, 0, 0, 300, 396, 495, 582, 700,
                                           792, 900, 990, 1100, 1164, 1300,
                                           1386, 1470, 1584, 1700, 1746, 1900,
                                           1980, 2100, 2134, 2300, 2328, 2475,
                                           2574, 2700, 2772, 2900, 2910, 3100,
                                           3168, 3300, 3366, 3465, 3492, 3700,
                                           3762, 3900, 3960, 4100, 4074, 4300,
                                           4268, 4410, 4554, 4700, 4656, 4900,
                                           4950, 5100, 5148, 5300, 5238, 5390,
                                           5544, 5700, 5742, 5900, 5820, 6100,
                                           6138, 6300, 6336, 6435, 6402, 6700,
                                           6732, 6900, 6930, 7100, 6984, 7300,
                                           7326, 7350, 7524, 7700, 7566, 7900,
                                           7920, 8100, 8118, 8300, 8148, 8415,
                                           8514, 8700, 8536, 8900, 8730, 9100,
                                           9108, 9300, 9306, 9405, 9312, 9700,
                                           9702, 9900 };

    boolean bPossible;
    double  dError;
    double  dUnitWidth;
    int     nIndex;

//System.out.println("Segment widths are "
//+ (dSegmentWidths[0] * 180.0 / Math.PI) + " "
//+ (dSegmentWidths[1] * 180.0 / Math.PI) + " "
//+ (dSegmentWidths[2] * 180.0 / Math.PI));

    for (nIndex = 3; nIndex < 100; nIndex++) {
      dUnitWidth = 2.0 * Math.PI / nIndex;

      dError = 0.0;

      bPossible = true;

      for (int i = 0; i < dSegmentWidths.length; i++) {
//        dError = Math.abs(dUnitWidth
//                          - dSegmentWidths[i]
//                            / Math.round(dSegmentWidths[i]
//                                         / dUnitWidth));

        dError = Math.abs(Math.round(dSegmentWidths[i] / dUnitWidth)
                          * dUnitWidth - dSegmentWidths[i]);
//System.out.println("Comparing " + dError + " to " + (2.0 * Math.PI / DENOMINATORS[nIndex]) + " for " + nIndex + " poles");

        if (dError > 2.0 * Math.PI / DENOMINATORS[nIndex]) {
          bPossible = false;

          break;
        } else {
//          System.out.println("OK");
        }
      }

      if (bPossible) {
        break;
      }
    }

//System.out.println("Possible pole count is " + nIndex);
    return nIndex;
  }
}

class Line {
  final double THETA;
  final double HEIGHT;

  public static Line createUsingSlopeAndYIntercept(double dSlope,
                                                   double dYIntercept) {
//ps.println("Using slope and y-intercept");
//ps.println("Slope is " + dSlope);
    return new Line(dSlope,
                    dYIntercept,
                    Type.SLOPE_AND_Y_INTERCEPT);
  }

  public static Line createUsingEndpoints(double dX1,
                                          double dY1,
                                          double dX2,
                                          double dY2) {
    return new Line(dX1,
                    dY1,
                    dX2,
                    dY2,
                    Type.END_POINTS);

  }

  public static Line bisectPoints(double dX1,
                                  double dY1,
                                  double dX2,
                                  double dY2) {
//    return new Line(dY1,
//                    -dX1,
//                    dY2,
//                    -dX2,
//                    Type.END_POINTS);
    double dMoveX;
    double dMoveY;

    dMoveX = (dX1 + dX2 - dY1 - dY2) / 2.0;
    dMoveY = (dX1 + dX2 + dY1 + dY2) / 2.0;

    return new Line(dY1 + dMoveX,
                    -dX1 + dMoveY,
                    dY2 + dMoveX,
                    -dX2 + dMoveY,
                    Type.END_POINTS);
  }

  private Line(double dX1,
               double dY1,
               double dX2,
               double dY2,
               Type   type) {
    double dDeltaX;
    double dDeltaY;
    double dHeight = Double.NaN;
    double dTheta = Double.NaN;

    switch (type) {
      case END_POINTS:
        dDeltaX = dX2 - dX1;
        dDeltaY = dY2 - dY1;

        // It is an error if the two points are co-located.
        if (   0 == dDeltaX
            && 0 == dDeltaY) {
          throw new IllegalArgumentException("Endpoints are co-located");
        }

        if (dDeltaX >= 0) {
          dTheta = Math.atan2(dDeltaY,
                              dDeltaX);
        } else {
          dTheta = Math.atan2(-dDeltaY,
                              -dDeltaX);
        }

        dHeight =   dY1 * Math.cos(dTheta)
                  - dX1 * Math.sin(dTheta);

        break;
    }

    THETA = dTheta;
    HEIGHT = dHeight;

//ps.println("(" + (THETA * 57.3) + "," + HEIGHT + ")");
  }

  private Line(double dValue1,
               double dValue2,
               Type   type) {
    double dHeight = Double.NaN;
    double dTheta = Double.NaN;

    switch (type) {
      case SLOPE_AND_Y_INTERCEPT:

        dTheta = Math.atan(dValue1);
        dHeight = dValue2 * Math.cos(dTheta);

        break;

      case INVERSE_SLOPE_AND_X_INTERCEPT:
        dTheta = Math.PI / 2.0 - Math.atan(dValue1);
        dHeight = dValue2 * Math.cos(dTheta);

        break;
    }

    THETA = dTheta;
//ps.println("Theta is " + (THETA * 57.3));
    HEIGHT = dHeight;
//ps.println("(" + (THETA * 57.3) + "," + HEIGHT + ")");
  }

  public double[] intersect(Line that) {
    double[] dIntersection = new double[2];

    intersect(that,
              dIntersection);

    return dIntersection;
  }

  public void intersect(Line     that,
                        double[] dIntersection) {
    double dCThis;
    double dCThat;
    double dDenominator;
    double dSThis;
    double dSThat;

    dCThis = Math.cos(this.THETA);
    dSThis = Math.sin(this.THETA);
    dCThat = Math.cos(that.THETA);
    dSThat = Math.sin(that.THETA);

    dDenominator = dSThis * dCThat - dSThat * dCThis;

    dIntersection[0] = (dCThis * that.HEIGHT - dCThat * this.HEIGHT)
                       / dDenominator;
    dIntersection[1] = (dSThis * that.HEIGHT - dSThat * this.HEIGHT)
                       / dDenominator;
//ps.println("("
//                   + (float) dIntersection[0]
//                   + ","
//                   + (float) dIntersection[1]
//                   + ")");
  }

  private enum Type {
    SLOPE_AND_Y_INTERCEPT,
    INVERSE_SLOPE_AND_X_INTERCEPT,
    END_POINTS;
  }
}