2017 ACM-ICPC 亚洲区（青岛赛区）网络赛 HDU 6206 1001 Apple（三角形外接圆圆心和半径）

题意：给你三个点，保证不再同一条直线上，再给你一点，问你是否在这三个点形成的圆外。

思路：就是求出三个点外接圆的圆心和半径判断下。精度问题需要用Java大数。

已知三点坐标，求外接圆圆心坐标与半径。

a=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)));

b=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2.0*((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1)));

r^2=(x1-a)*(x1-a)+(y1-b)*(y1-b);

内接圆圆心坐标和半径：

设:在三角形ABC中,三顶点的坐标为：A(x1,y1),B(x2,y2),C(x3,y3) BC=a,CA=b,AB=c
内心为M （X,Y） 
M（（aX1+bX2+cX3)/(a+b+c),（aY1+bY2+cY3)/(a+b+c)）

半径：1/2*sqrt( (a+b-c)*(a+c-b)*(b+c-a) / (a+b+c) ), a b c为三边长

代码:

import java.math.BigDecimal;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigDecimal x1, y1, x2, y2, x3, y3, x4, y4;
        int _;
        _ = sc.nextInt();
        while(_-- != 0)
        {
            x1 = sc.nextBigDecimal();
            y1 = sc.nextBigDecimal();
            x2 = sc.nextBigDecimal();
            y2 = sc.nextBigDecimal();
            x3 = sc.nextBigDecimal();
            y3 = sc.nextBigDecimal();
            x4 = sc.nextBigDecimal();
            y4 = sc.nextBigDecimal();
            BigDecimal t;
            if(y3.equals(y1))
            {
                t = y2;
                y2 = y3;
                y3 = t;

                t = x2;
                x2 = x3;
                x3 = t;
            }
            BigDecimal t1 = (y3.subtract(y1)).multiply(y2.multiply(y2).subtract(y1.multiply(y1)));
            BigDecimal t2 = (y3.subtract(y1)).multiply(x2.multiply(x2).subtract(x1.multiply(x1)));
            BigDecimal t3 = (y1.subtract(y2)).multiply(y1.multiply(y1).subtract(y3.multiply(y3)));
            BigDecimal t4 = (y1.subtract(y2)).multiply(x1.multiply(x1).subtract(x3.multiply(x3)));
            BigDecimal t5 = BigDecimal.valueOf(2).multiply(y1.subtract(y2)).multiply(x3.subtract(x1));
            BigDecimal t6 = BigDecimal.valueOf(2).multiply(y3.subtract(y1)).multiply(x1.subtract(x2));
            BigDecimal x0 = (t1.add(t2).subtract(t3).subtract(t4)).divide(t5.subtract(t6));

            BigDecimal v1 = y3.multiply(y3);
            BigDecimal v2 = y1.multiply(y1);
            BigDecimal v3 = BigDecimal.valueOf(2).multiply(x0).multiply(x3.subtract(x1));
            BigDecimal v4 = x1.multiply(x1);
            BigDecimal v5 = x3.multiply(x3);
            BigDecimal v6 = BigDecimal.valueOf(2).multiply(y3.subtract(y1));
//            System.out.println(v6);
            BigDecimal y0 = (v1.subtract(v2).subtract(v3).subtract(v4).add(v5)).divide(v6);

            BigDecimal z1 = (y0.subtract(y2)).multiply(y0.subtract(y2));
            BigDecimal z2 = (x0.subtract(x2)).multiply(x0.subtract(x2));
            BigDecimal r = z1.add(z2);

            BigDecimal tmp1 = (x4.subtract(x0)).multiply(x4.subtract(x0));
            BigDecimal tmp2 = (y4.subtract(y0)).multiply(y4.subtract(y0));
            BigDecimal dis = tmp1.add(tmp2);
            if(dis.compareTo(r) > 0)
            {
                System.out.println("Accepted");
            }
            else
            {
                System.out.println("Rejected");
            }

        }
    }
}