（高精度/Java）HDU 6206 Apple

Apple

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 488 Accepted Submission(s): 160

Problem Description

Apple is Taotao's favourite fruit. In his backyard, there are three apple trees with coordinates

Input

The first line contains an integer

Output

For each case, output "Accepted" if the position is outside the circle, or "Rejected" if the position is on or inside the circle.

Sample Input

3 -2 0 0 -2 2 0 2 -2 -2 0 0 -2 2 0 0 2 -2 0 0 -2 2 0 1 1

Sample Output

Accepted Rejected Rejected

Source

2017 ACM/ICPC Asia Regional Qingdao Online

利用同弧所对圆周角相等，不妨设需要判断的D点与B点在AC同侧，则只需要比较∠ABC与∠ADC的大小，利用余弦定理可以很轻松表示起来，只有cosD比cosB大时，D比B小，点D在△ABC外接圆外。为避免开方运算，同时平方（其中一些正负的判断细节需要注意）再比较。

判断是否在同侧只需要算一下叉积，D、B关于AC叉积如果具有相同正负性即在同侧。

  1 //package com.company;
  2 
  3 import java.math.BigInteger;
  4 import java.util.Scanner;
  5 
  6 public class Main {
  7     public static BigInteger lo(BigInteger x,BigInteger y,BigInteger sx,BigInteger sy,BigInteger ex,BigInteger ey)
  8     {
  9         return x.subtract(sx).multiply(ey.subtract(sy)).subtract(ex.subtract(sx).multiply(y.subtract(sy)));
 10         //return ey.multiply(x).subtract(sy.multiply(x)).add(sy.multiply(ex)).subtract(sx.multiply(ey)).subtract(y.multiply(ex)).add(sx.multiply(y));
 11     }
 12     public static boolean check(BigInteger sx,BigInteger sy,BigInteger ex,BigInteger ey,BigInteger tx,BigInteger ty,BigInteger tx2,BigInteger ty2)
 13     {
 14         if(lo(tx2,ty2,sx,sy,ex,ey).multiply(lo(tx,ty,sx,sy,ex,ey)).compareTo(BigInteger.ZERO)>0)
 15             return true;
 16         else return false;
 17     }
 18     public static void main(String[] args) {
 19     // write your code here
 20         Scanner sc=new Scanner(System.in);
 21         BigInteger x1,y1,x2,y2,x3,y3,x4,y4;
 22         BigInteger ab,ac,bc,ad,cd,bd,lin1,lin2;
 23         BigInteger tem1,tem2,an;
 24         int t=sc.nextInt();
 25         for(int k=0;k<t;k++)
 26         {
 27             x1=sc.nextBigInteger();
 28             y1=sc.nextBigInteger();
 29             x2=sc.nextBigInteger();
 30             y2=sc.nextBigInteger();
 31             x3=sc.nextBigInteger();
 32             y3=sc.nextBigInteger();
 33             x4=sc.nextBigInteger();
 34             y4=sc.nextBigInteger();
 35             ab=x1.subtract(x2).pow(2).add(y1.subtract(y2).pow(2));
 36             ac=x1.subtract(x3).pow(2).add(y1.subtract(y3).pow(2));
 37             bc=x2.subtract(x3).pow(2).add(y2.subtract(y3).pow(2));
 38             bd=x2.subtract(x4).pow(2).add(y2.subtract(y4).pow(2));
 39             ad=x1.subtract(x4).pow(2).add(y1.subtract(y4).pow(2));
 40             cd=x3.subtract(x4).pow(2).add(y3.subtract(y4).pow(2));
 41             if(check(x1,y1,x3,y3,x2,y2,x4,y4))//compare with ABC
 42             {
 43                 lin1=ab.add(bc).subtract(ac);//numerator of B
 44                 lin2=ad.add(cd).subtract(ac);//numerator of D
 45                 if(lin1.compareTo(BigInteger.ZERO)>0 && lin2.compareTo(BigInteger.ZERO)<=0)
 46                 {
 47                     System.out.println("Rejected");
 48                     continue;
 49                 }
 50                 else if(lin1.compareTo(BigInteger.ZERO)<=0 && lin2.compareTo(BigInteger.ZERO)>0)
 51                 {
 52                     System.out.println("Accepted");
 53                     continue;
 54                 }
 55                 tem1=lin1.pow(2).multiply(ad).multiply(cd);
 56                 tem2=lin2.pow(2).multiply(ab).multiply(bc);
 57                 an=tem1.subtract(tem2);
 58                 if(lin1.compareTo(BigInteger.ZERO)<0 && lin2.compareTo(BigInteger.ZERO)<0)
 59                 {
 60                     if(an.compareTo(BigInteger.ZERO)>0)
 61                     {
 62                         System.out.println("Accepted");
 63                         continue;
 64                     }
 65                     else
 66                     {
 67                         System.out.println("Rejected");
 68                         continue;
 69                     }
 70                 }
 71                 else if(an.compareTo(BigInteger.ZERO)<0)
 72                 {
 73                     System.out.println("Accepted");
 74                     continue;
 75                 }
 76                 else
 77                 {
 78                     System.out.println("Rejected");
 79                     continue;
 80                 }
 81             }
 82             else if(check(x1,y1,x2,y2,x3,y3,x4,y4))
 83             {
 84                 lin1=ac.add(bc).subtract(ab);
 85                 lin2=ad.add(bd).subtract(ab);
 86                 if(lin1.compareTo(BigInteger.ZERO)>0 && lin2.compareTo(BigInteger.ZERO)<=0)
 87                 {
 88                     System.out.println("Rejected");
 89                     continue;
 90                 }
 91                 else if(lin1.compareTo(BigInteger.ZERO)<=0 && lin2.compareTo(BigInteger.ZERO)>0)
 92                 {
 93                     System.out.println("Accepted");
 94                     continue;
 95                 }
 96                 tem1=lin1.pow(2).multiply(ad).multiply(bd);
 97                 tem2=lin2.pow(2).multiply(ac).multiply(bc);
 98                 an=tem1.subtract(tem2);
 99                 if(lin1.compareTo(BigInteger.ZERO)<0 && lin2.compareTo(BigInteger.ZERO)<0)
100                 {
101                     if(an.compareTo(BigInteger.ZERO)>0)
102                     {
103                         System.out.println("Accepted");
104                         continue;
105                     }
106                     else
107                     {
108                         System.out.println("Rejected");
109                         continue;
110                     }
111                 }
112                 else if(an.compareTo(BigInteger.ZERO)<0)
113                 {
114                     System.out.println("Accepted");
115                     continue;
116                 }
117                 else
118                 {
119                     System.out.println("Rejected");
120                     continue;
121                 }
122             }
123             else if(check(x2,y2,x3,y3,x1,y1,x4,y4))
124             {
125                 lin1=ab.add(ac).subtract(bc);
126                 lin2=bd.add(cd).subtract(bc);
127                 if(lin1.compareTo(BigInteger.ZERO)>0 && lin2.compareTo(BigInteger.ZERO)<=0)
128                 {
129                     System.out.println("Rejected");
130                     continue;
131                 }
132                 else if(lin1.compareTo(BigInteger.ZERO)<=0 && lin2.compareTo(BigInteger.ZERO)>0)
133                 {
134                     System.out.println("Accepted");
135                     continue;
136                 }
137                 tem1=lin1.pow(2).multiply(bd).multiply(cd);
138                 tem2=lin2.pow(2).multiply(ab).multiply(ac);
139                 an=tem1.subtract(tem2);
140                 if(lin1.compareTo(BigInteger.ZERO)<0 && lin2.compareTo(BigInteger.ZERO)<0)
141                 {
142                     if(an.compareTo(BigInteger.ZERO)>0)
143                     {
144                         System.out.println("Accepted");
145                         continue;
146                     }
147                     else
148                     {
149                         System.out.println("Rejected");
150                         continue;
151                     }
152                 }
153                 else if(an.compareTo(BigInteger.ZERO)<0)
154                 {
155                     System.out.println("Accepted");
156                     continue;
157                 }
158                 else
159                 {
160                     System.out.println("Rejected");
161                     continue;
162                 }
163             }
164             else
165             {
166                 System.out.println("Rejected");
167                 continue;
168             }
169         }
170     }
171 }