HDU-6206 Apple(Java练习)

题目传送门:HDU-6206

题意:

输入求第四个点是否在前三个点构成的圆外,是的话输出Accepted
在圆内或者圆上输出Rejected
因为数据范围较大,Java的BigDecimal再合适不过。

圆心为(rx,ry)
rx1 = (x1^2-x2^2+y1^2-y2^2)(y1-y3)-(x1^2-x3^2+y1^2-y3^2)(y1-y2)
rx2 = 2(y1-y3)(x1-x2)-2(y1-y2)(x1-x3)
rx = rx1/rx2
ry1 = (x1^2-x2^2+y1^2-y2^2)(x1-x3)-(x1^2-x3^2+y1^2-y3^2)(x1-x2)
ry2 = 2(x1-x3)(y1-y2)-2(x1-x2)(y1-y3)
ry = ry1 / ry2

网上的公式:

实际上还有更简便的方法,直接能用更直接的公式算出圆心 (x0, y0) 和半径的平方 r^2
x0=((y2-y1)(y3y3-y1y1+x3x3-x1x1)-(y3-y1)(y2y2-y1y1+x2x2-x1x1))/(2.0((x3-x1)(y2-y1)-(x2-x1)(y3-y1)));
y0=((x2-x1)
(x3x3-x1x1+y3y3-y1y1)-(x3-x1)(x2x2-x1x1+y2y2-y1y1))/(2.0((y3-y1)(x2-x1)-(y2-y1)(x3-x1)));
r^2=(x1-x0)(x1-x0)+(y1-y0)(y1-y0);

##Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
BigDecimal x1, y1, x2, y2, x3, y3, x, y;
Scanner cin = new Scanner(System.in);
int t;
t = cin.nextInt();
for(int i = 0 ; i < t ; i ++) {
x1 = cin.nextBigDecimal();
y1 = cin.nextBigDecimal();
x2 = cin.nextBigDecimal();
y2 = cin.nextBigDecimal();
x3 = cin.nextBigDecimal();
y3 = cin.nextBigDecimal();
x = cin.nextBigDecimal();
y = cin.nextBigDecimal();
BigDecimal t1,t2,t3;
BigDecimal tt1,tt2,tt3;
t1 = x1.pow(2).subtract(x2.pow(2));
t2 = x2.pow(2).subtract(x3.pow(2));
t3 = x1.pow(2).subtract(x3.pow(2));
tt1 = y1.pow(2).subtract(y2.pow(2));
tt2 = y2.pow(2).subtract(y3.pow(2));
tt3 = y1.pow(2).subtract(y3.pow(2));
BigDecimal q1,q2,q3,qq1,qq2,qq3;
q1 = x1.subtract(x2);
q2 = x2.subtract(x3);
q3 = x1.subtract(x3);
qq1 = y1.subtract(y2);
qq2 = y2.subtract(y3);
qq3 = y1.subtract(y3);
BigDecimal rx, ry;
rx = ((t1.add(tt1)).multiply(qq3)).subtract(t3.add(tt3).multiply(qq1));
BigDecimal ans1,ans2;
ans1 = qq3.multiply(q1).subtract((qq1.multiply(q3)));
ans1 = ans1.multiply(BigDecimal.valueOf(2.0));
rx = rx.divide(ans1);
ry = ((t1.add(tt1)).multiply(q3)).subtract(t3.add(tt3).multiply(q1));
ans2 = q3.multiply(qq1).subtract((q1.multiply(qq3)));
ans2 = ans2.multiply(BigDecimal.valueOf(2.0));
ry = ry.divide(ans2);
BigDecimal R = CalR(x1, y1, rx, ry);
BigDecimal rood = CalR(x, y, rx, ry);
if (rood.compareTo(R) <= 0 ) {
System.out.println("Rejected");
} else {
System.out.println("Accepted");
}
}
}

public static BigDecimal CalR(BigDecimal x1, BigDecimal y1, BigDecimal rx, BigDecimal ry) {
BigDecimal c = (x1.subtract(rx)).multiply(x1.subtract(rx));
BigDecimal d = (y1.subtract(ry)).multiply(y1.subtract(ry));
return c.add(d);
}

}