Aizu Online Judge 0129 Hide-and-Seek Supporting System

■0129 Hide-and-Seek Supporting System

鬼-たろう君からなる直線と円の交点を求めて，交点が鬼-たろう君からなる線分上に存在するかを判定するだけ．

view plainprint?

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;
 P[] cs;
 int[] rs;
 P t, s;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   cs=new P[n];
   rs=new int[n];
   for(int i=0; i<n; i++){
    int x=sc.nextInt();
    int y=sc.nextInt();
    rs[i]=sc.nextInt();
    cs[i]=new P(x, y);
   }
   m=sc.nextInt();
   for(int i=0; i<m; i++){
    int tx=sc.nextInt();
    int ty=sc.nextInt();
    int sx=sc.nextInt();
    int sy=sc.nextInt();
    t=new P(tx, ty);
    s=new P(sx, sy);
    solve();
   }
  }
 }

 void solve(){
  boolean safe=false;
  for(int i=0; i<n; i++){
   P[] ps=isCL(cs[i], rs[i], t, s);
   for(P p : ps){
    if(between(t.x, s.x, p.x)&&between(t.y, s.y, p.y)){
     safe=true;
    }
   }
  }
  println(safe?"Safe":"Danger");
 }

 boolean between(double x1, double x2, double x){
  return (x1<x+EPS&&x<x2+EPS)||(x1+EPS>x&&x+EPS>x2);
 }

 P[] isCL(P c, double r, P p1, P p2){
  double x=p1.sub(c).dot(p2.sub(p1));
  double y=p2.sub(p1).abs2();
  double d=x*x-y*(p1.sub(c).abs2()-r*r);
  if(d<-EPS)
   return new P[0];
  if(d<0)
   d=0;
  P q1=p1.sub(p2.sub(p1).mul(x/y));
  P q2=p2.sub(p1).mul(Math.sqrt(d)/y);
  return new P[]{q1.sub(q2), q1.add(q2)};
 }

 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();
 }
}