Aizu Online Judge 0143 Altair and Vega

■0143 Altair and Vega

牽牛と織女を結ぶ線分が，三角形を構成する線分と何回交差するかで答えは決まる．

0，2回：遮断されていない
1回：遮断されている

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  P ps1, ps2, ps3;  
18.  P k, s;  
19.   
20.  void run(){  
21.   n=sc.nextInt();  
22.   for(int i=0; i<n; i++){  
23.    int xp1=sc.nextInt();  
24.    int yp1=sc.nextInt();  
25.    int xp2=sc.nextInt();  
26.    int yp2=sc.nextInt();  
27.    int xp3=sc.nextInt();  
28.    int yp3=sc.nextInt();  
29.    int xk=sc.nextInt();  
30.    int yk=sc.nextInt();  
31.    int xs=sc.nextInt();  
32.    int ys=sc.nextInt();  
33.    ps1=new P(xp1, yp1);  
34.    ps2=new P(xp2, yp2);  
35.    ps3=new P(xp3, yp3);  
36.    k=new P(xk, yk);  
37.    s=new P(xs, ys);  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   if(crsSS(k, s, ps1, ps2)^crsSS(k, s, ps2, ps3)^crsSS(k, s, ps3, ps1)){  
44.    println("OK");  
45.   }else{  
46.    println("NG");  
47.   }  
48.  }  
49.   
50.  boolean crsSS(P p1, P p2, P q1, P q2){  
51.   if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))  
52.    return false;  
53.   if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))  
54.    return false;  
55.   if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))  
56.    return false;  
57.   if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))  
58.    return false;  
59.   return signum(p2.sub(p1).det(q1.sub(p1)))  
60.     *signum(p2.sub(p1).det(q2.sub(p1)))<EPS  
61.     &&signum(q2.sub(q1).det(p1.sub(q1)))  
62.       *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;  
63.  }  
64.   
65.  class P{  
66.   double x, y;  
67.   
68.   P(){  
69.    this(0, 0);  
70.   }  
71.   
72.   P(double x, double y){  
73.    this.x=x;  
74.    this.y=y;  
75.   }  
76.   
77.   P add(P p){  
78.    return new P(x+p.x, y+p.y);  
79.   }  
80.   
81.   P sub(P p){  
82.    return new P(x-p.x, y-p.y);  
83.   }  
84.   
85.   P mul(double m){  
86.    return new P(x*m, y*m);  
87.   }  
88.   
89.   P div(double d){  
90.    return new P(x/d, y/d);  
91.   }  
92.   
93.   double abs(){  
94.    return Math.sqrt(abs2());  
95.   }  
96.   
97.   double abs2(){  
98.    return x*x+y*y;  
99.   }  
100.   
101.   double arg(){  
102.    return Math.atan2(y, x);  
103.   }  
104.   
105.   // inner product  
106.   double dot(P p){  
107.    return x*p.x+y*p.y;  
108.   }  
109.   
110.   // outer product  
111.   double det(P p){  
112.    return x*p.y-y*p.x;  
113.   }  
114.   
115.   P rot90(){  
116.    return new P(-y, x);  
117.   }  
118.   
119.   // conjugation  
120.   P conj(){  
121.    return new P(x, -y);  
122.   }  
123.  }  
124.   
125.  void debug(Object... os){  
126.   System.err.println(Arrays.deepToString(os));  
127.  }  
128.   
129.  void print(String s){  
130.   System.out.print(s);  
131.  }  
132.   
133.  void println(String s){  
134.   System.out.println(s);  
135.  }  
136.   
137.  public static void main(String[] args){  
138.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
139.   new Main().run();  
140.  }  
141. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 P ps1, ps2, ps3;
 P k, s;

 void run(){
  n=sc.nextInt();
  for(int i=0; i<n; i++){
   int xp1=sc.nextInt();
   int yp1=sc.nextInt();
   int xp2=sc.nextInt();
   int yp2=sc.nextInt();
   int xp3=sc.nextInt();
   int yp3=sc.nextInt();
   int xk=sc.nextInt();
   int yk=sc.nextInt();
   int xs=sc.nextInt();
   int ys=sc.nextInt();
   ps1=new P(xp1, yp1);
   ps2=new P(xp2, yp2);
   ps3=new P(xp3, yp3);
   k=new P(xk, yk);
   s=new P(xs, ys);
   solve();
  }
 }

 void solve(){
  if(crsSS(k, s, ps1, ps2)^crsSS(k, s, ps2, ps3)^crsSS(k, s, ps3, ps1)){
   println("OK");
  }else{
   println("NG");
  }
 }

 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

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

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}