首页 > ACM题库 > HDU-杭电 > HDU 4378-The battle on X-Star[解题报告]HOJ
2015
05-24

HDU 4378-The battle on X-Star[解题报告]HOJ

The battle on X-Star

问题描述 :

There is a special planet in universe called "X-Star". The X-Star is a regular sphere with a radius of R meters. Unfortunately, a tremendous battle is in progress on "X-Star". Many aliens were landed on X-Star and find their unique place to settle down. Each alien’s place can be defined as latitude and longitude of the "X-Star". These aliens have a special magical skill, which is extremely powerful. This skill can only be released by two different aliens. After it was released, there will occur a great circle on the plant’s surface, which just through the place between the two aliens who have released it. That is to say, the great circle will pass the middle point between their places and have same distance to the two aliens.
Sub Sequence

The great circle will exert a special force, which will affect the general of X-Star. The general of X-Star now is governing the army, and he will have a velocity of h*k*v0 m/s (here k is a constant value and v0 is the general’s normal speed) when his distance to the great circle is h due to the special force, in other words, h is the height of his current location to the plane of the great circle. The wise general will take this action when the great circle occurs: run away from the great circle as far as possible (here "run" means move on the X-Star’s surface), no matter there will be some aliens or not. Now he need to know when two certain aliens released the skill, how many seconds does he needed to take his action from several certain location at least.
There will be n aliens landed on X-Star and the general will ask you m possible scenarios.

输入:

Multiple test cases, process to the end of input.
For every case, there are several lines.
The first line is two integer n (1 ≤ n ≤ 10000) and m (1 ≤ m ≤ 1000) and a real number R (0 < R ≤ 1e11) as described above.
The following n lines contain the aliens’ settled places. Each line have two real number, which represents the i-th (i started from 0) alien’s latitude and longitude on the X-Star.
The following 3*m lines contain m possible scenarios. Each scenario contains three lines, the first line is two different aliens’ indices (started from 0) who will release the skill, and the second line is the general’s current location’s latitude and longitude, and the third line contains k (0 ≤ k ≤ 5) and v0 (0 ≤ v0 ≤ 5) described above.
All latitudes are between -90 and 90 inclusive, and all longitudes are between -180 and 180 inclusive. It is guaranteed that all the aliens’ locations are different from each other.

输出:

Multiple test cases, process to the end of input.
For every case, there are several lines.
The first line is two integer n (1 ≤ n ≤ 10000) and m (1 ≤ m ≤ 1000) and a real number R (0 < R ≤ 1e11) as described above.
The following n lines contain the aliens’ settled places. Each line have two real number, which represents the i-th (i started from 0) alien’s latitude and longitude on the X-Star.
The following 3*m lines contain m possible scenarios. Each scenario contains three lines, the first line is two different aliens’ indices (started from 0) who will release the skill, and the second line is the general’s current location’s latitude and longitude, and the third line contains k (0 ≤ k ≤ 5) and v0 (0 ≤ v0 ≤ 5) described above.
All latitudes are between -90 and 90 inclusive, and all longitudes are between -180 and 180 inclusive. It is guaranteed that all the aliens’ locations are different from each other.

样例输入:

2 3 6380000.0
5.5 0.0
-5.5 0.0
0 1
9.99 50.5
0.5 0.5
0 1
10.0 99.0
0.0 1.11
0 1
90.0 0.0
1.0 1.0

2 1 3450.0
55.5 -77.8
-44.4 140.6
0 1
12.3 -66.6
1.0 1.0

样例输出:

9.749
God Bless Him!
0.000

0.766

/** Micro Mezzo Macro Flation -- Overheated Economy ., Last Update: Dec. 20th 2012 **/ //{

/** Header .. **/ //{
#define LOCAL

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (int n____=(i=0,int(n));i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i>=a____;--i)

#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, nxt) for (int i=hd;i;i=nxt[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define BSC(A, x) (lower_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define fi first
#define se second

#define Rush for(int ____T=RD(); ____T--;)

#define Display(A, n, m) {                      \
	REP(i, n){		                            \
        REP(j, m) cout << A[i][j] << " ";       \
        cout << endl;				            \
	}						                    \
}

#define Display_1(A, n, m) {				    \
	REP_1(i, n){		                        \
        REP_1(j, m) cout << A[i][j] << " ";     \
		cout << endl;		            		\
	}						                    \
}

#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define Ruby system("ruby main.rb")
#define Haskell system("runghc main.hs")
#define Python system("python main.py")
#define Pascal system("fpc main.pas")

typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

template<class T> inline T& RD(T &);
template<class T> inline void OT(const T &);
inline LL RD(){LL x; return RD(x);}
inline DB& RF(DB &x){scanf("%lf", &x); return x;}
inline DB RF(){DB x; return RF(x);}
inline char* RS(char *s);
inline char& RC(char &c);
inline char RC();
inline char& RC(char &c){scanf(" %c", &c); return c;}
inline char RC(){char c; return RC(c);}
//inline char& RC(char &c){c = getchar(); return c;}
//inline char RC(){return getchar();}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}
template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}
template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}
template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}
template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}
inline char& RC(char &a, char &b){RC(a), RC(b); return a;}
inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}
inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}
inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}
inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}
inline void RS(char *s1, char *s2){RS(s1), RS(s2);}
inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}
template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(T &A){A.clear();}
template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}
template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}
template<class T, class C> inline T& SRT(T &A, C B){sort(ALL(A), B); return A;}
template<class T> inline T& UNQ(T &A){A.resize(unique(ALL(SRT(A))) - A.begin());return A;}

//}

/** Constant List .. **/ //{

const int MOD = 1000000007;
//int MOD = 99990001;
const int INF = 0x3f3f3f3f;
const LL INFF = 1LL << 60;
const DB EPS = 1e-9;
const DB OO = 1e15;
const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

//}

/** Add On .. **/ //{
// <<= '0. Nichi Joo ., //{
template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (a<b) a=b;}
template<class T> inline void checkMin(T &a, T &b, const T x){checkMin(a, x), checkMin(b, x);}
template<class T> inline void checkMax(T &a, T &b, const T x){checkMax(a, x), checkMax(b, x);}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
inline int Ceil(int x, int y){return (x - 1) / y + 1;}
//}
// <<= '1. Bitwise Operation ., //{
namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}
inline bool _1(LL x, int i){return bool(x&1LL<<i);}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);
    return x;
}

inline LL reverse_bits(LL x){
    x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
    x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
    x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
    x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
    x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);
    x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);
    return x;
}

template<class T> inline bool odd(T x){return x&1;}
template<class T> inline bool even(T x){return !odd(x);}
template<class T> inline T low_bit(T x) {return x & -x;}
template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}
template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}

inline int low_idx(int x){return __builtin_ffs(x);}
inline int low_idx(LL x){return __builtin_ffsll(x);}
inline int high_idx(int x){return low_idx(reverse_bits(x));}
inline int high_idx(LL x){return low_idx(reverse_bits(x));}
inline int clz(int x){return __builtin_clz(x);}
inline int clz(LL x){return __builtin_clzll(x);}
inline int ctz(int x){return __builtin_ctz(x);}
inline int ctz(LL x){return __builtin_ctzll(x);}
inline int parity(int x){return __builtin_parity(x);}
inline int parity(LL x){return __builtin_parityll(x);}
inline int lg2(int a){return 31 - clz(a);}
inline int lg2(LL a){return 63 - clz(a);}
inline int count_bits(int x){return __builtin_popcount(x);}
inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}
namespace SL{
    namespace KMP{

        void calc_pi(const char *P, int n, int *pi){
            for (int i = 1, j = pi[0] = -1; i < n; ++i){
                while (j >= 0 && P[i] != P[j+1]) j = pi[j];
                if (P[i] == P[j+1]) ++j;
                pi[i] = j;
            }
            //REP(i, n) cout << pi[i] << " "; cout << endl;
        }

        bool run(const char *T, int n, const char *P, int m, const int *pi){
            for (int i = 0, j = -1; i < n; ++i){
                while (j >= 0 && T[i] != P[j+1]) j = pi[j];
                if (T[i] == P[j+1]) ++j;
                if (j == m - 1) return true;
            }
            return false;
        }

    } //using namespace KMP;

    namespace Z{
        void calc_z(const char *P, int n, int *z){

            z[0] = n;

            for (int i = 1, l = 0, r = 0; i < n; ++i){
                if (i > r){
                    for(l = r = i; r < n && P[r] == P[r - l];) ++r;
                    z[i] = r - l, --r;
                }
                else {
                    if (z[i - l] < r - i + 1) z[i] = z[i - l];
                    else {
                        for (l = i;r < n && P[r] == P[r - l];) ++r;
                        z[i] = r - l, --r;
                    }
                }
            }

            //REP(i, n) cout << z[i] << " "; cout << endl;
        }

        int run(const char *T, int n, const char *P, int m, const int *z){

            int ex; REP_C_N(ex, min(n, m)) if (T[ex] != P[ex]) break;

            int res = ex == m;

            for (int i = 1, l = 0, r = 0; i < n; ++i){
                if (i > r){
                    for (l = r = i; r < n && T[r] == P[r - l];) ++r;
                    ex = r - l, --r;
                }
                else {
                    if (z[i - l] < r - i + 1) ex = z[i - l];
                    else {
                        for (l = i; r < n && T[r] == P[r - l];) ++r;
                        ex = r - l, --r;
                    }
                }
                if (ex == m) ++res;
            }

            return res;
        }
    } //using namespace Z;

    void Manacher(char s[], int n, int p[]){
        const int NN = 0;
        static char ss[NN*2+2]; int nn = 2*n+2;
        ss[0] = '$', ss[nn-1] = '#', ss[nn] = 0;
        REP(i, n) ss[i*2+1] ='#', ss[i*2+2] = s[i];
        int mx = 0, id = 0; FOR(i, 1, nn){
            p[i] = mx > i ? min(p[2*id-i], mx - i) : 1;
            while (ss[i+p[i]] == ss[i-p[i]]) ++p[i];
            if (i + p[i] > mx) mx = i + p[i], id = i;
        }
    }

} //using namespace SL;//}
// <<= '9. Comutational Geometry .,//{
namespace CG{

struct Po; struct Line; struct Seg;

inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

struct Po{
    DB x, y; Po(DB _x=0, DB _y=0):x(_x), y(_y){}
    friend istream& operator >>(istream& in, Po &p){return in >> p.x >> p.y;}
    friend ostream& operator <<(ostream& out, Po p){return out << "(" << p.x << ", " << p.y << ")";}
    bool operator ==(const Po& r)const{return !sgn(x-r.x) && !sgn(y-r.y);};
    bool operator !=(const Po& r)const{return sgn(x-r.x) || sgn(y-r.y);}
    Po operator +(const Po& r)const{return Po(x+r.x, y+r.y);}
    Po operator -(const Po& r)const{return Po(x+r.x, y+r.y);}
    Po operator *(DB k)const{return Po(x*k,y*k);}
    Po operator /(DB k)const{return Po(x/k,y/k);}
    DB operator *(const Po&) const;
    DB operator ^(const Po&) const;

    bool operator <(const Po &r) const{return sgn(x,r.x)<0||!sgn(x,r.x)&&sgn(y,r.y)<0;}
    Po operator -()const{return Po(-x,-y);}
    Po& operator +=(const Po &r){x+=r.x,y+=r.y;return *this;}
    Po& operator -=(const Po &r){x-=r.x,y-=r.y;return *this;}
    Po& operator *=(DB k){x*=k,y*=k;return*this;}
    Po& operator /=(DB k){x/=k,y/=k;return*this;}

    DB length_sqr()const{return sqr(x)+sqr(y);}
    DB length()const{return sqrt(length_sqr());}
    Po unit()const{return *this/length();}
    bool dgt()const{return !sgn(x)&&!sgn(y);}
    DB atan()const{return atan2(y,x);}
    void input(){RF(x,y);}
};

Po operator *(DB k, Po a){return a * k;}

struct Line{
    Po a, b;
    Line(DB x0=0, DB y0=0, DB x1=0, DB y1=0):a(Po(x0, y0)), b(Po(x1, y1)){}
    Line(const Po &a, const Po &b):a(a), b(b){}
    Line(const Line &l):a(l.a), b(l.b){}

    friend ostream& operator <<(ostream& out, Line p){return out << p.a << "-" << p.b;}
    Line operator +(Po x)const{return Line(a + x, b + x);}
    DB length()const{return (b-a).length();}
    bool dgt()const{return (b-a).dgt();}
    void input(){a.input(), b.input();}
    void getequation(DB, DB, DB) const;
};

struct Seg: Line{
};

#define innerProduct dot
#define scalarProduct dot
#define dotProduct dot
#define outerProduct det
#define crossProduct det

inline DB dot(const DB &x1, const DB &y1, const DB &x2, const DB &y2){return x1 * x2 + y1 * y2;}
inline DB dot(const Po &a, const Po &b){return dot(a.x, a.y, b.x, b.y);}
inline DB dot(const Po &p0, const Po &p1, const Po &p2){return dot(p1 - p0, p2 - p0);}
inline DB dot(const Po &o, const Line &l){return dot(o, l.a, l.b);}
inline DB dot(const Line &l, const Po &o){return dot(o, l.a, l.b);}
inline DB dot(const Line &l1, const Line &l2){return dot(l1.b - l1.a, l2.b - l2.a);}

inline DB det(const DB &x1, const DB &y1, const DB &x2, const DB &y2){return x1 * y2 - x2 * y1;}
inline DB det(const Po &a, const Po &b){return det(a.x, a.y, b.x, b.y);}
inline DB det(const Po &p0, const Po &p1, const Po &p2){return det(p1 - p0, p2 - p0);}
inline DB det(const Po &o, const Line &l){return det(o, l.a, l.b);}
inline DB det(const Line &l, const Po &o){return det(o, l.a, l.b);}
inline DB det(const Line &l1, const Line &l2){return det(l1.b - l1.a, l2.b - l2.a);}

DB Po::operator *(const Po &r)const{return dot(*this, r);}
DB Po::operator ^(const Po &r)const{return det(*this, r);}

void Line::getequation(DB A, DB B, DB C) const{
    A = a.y - b.y, B = b.x - a.x, C = det(a, b);
}

template<class T1, class T2> inline DB dist(const T1 &x, const T2 &y){return sqrt(dist_sqr(x, y));}
template<class T1, class T2, class T3> inline DB dist(const T1 &x, const T2 &y, const T3 &z){return sqrt(dist_sqr(x, y, z));}
template<class T1, class T2> inline int dett(const T1 &x, const T2 &y){return sgn(det(x, y));}
template<class T1, class T2> inline int dott(const T1 &x, const T2 &y){return sgn(dot(x, y));}
template<class T1, class T2, class T3> inline int dett(const T1 &x, const T2 &y, const T3 &z){return sgn(det(x, y, z));}
template<class T1, class T2, class T3> inline int dott(const T1 &x, const T2 &y, const T3 &z){return sgn(dot(x, y, z));}
template<class T1, class T2, class T3, class T4> inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(det(x, y, z, w));}
template<class T1, class T2, class T3, class T4> inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(dot(x, y, z, w));}

inline DB dist_sqr(const DB &x, const DB &y){return sqr(x) + sqr(y);}
inline DB dist_sqr(const DB &x, const DB &y, const DB &z){return sqr(x) + sqr(y) + sqr(z);}
inline DB dist_sqr(const Po &a, const Po &b){return sqr(a.x - b.x) + sqr(a.y - b.y);}
inline DB dist_sqr(const Po &p, const Line &l){Po v0 = l.b - l.a, v1 = p - l.a; return sqr(fabs(det(v0, v1))) / v0.length_sqr();}
inline DB dist_sqr(const Po &p, const Seg &l){
    Po v0 = l.b - l.a, v1 = p - l.a, v2 = p - l.b;
    if (sgn(dot(v0, v1)) * sgn(dot(v0, v2)) <= 0) return dist_sqr(p, Line(l));
    else return min(v1.length_sqr(), v2.length_sqr());
}
inline DB dist_sqr(Line l, Po p){return dist_sqr(p, l);}
inline DB dist_sqr(Seg l, Po p){return dist_sqr(p, l);}
inline DB dist_sqr(Line l1, Line l2){
    if (sgn(det(l1, l2)) != 0) return 0;
    return dist_sqr(l1.a, l2);
}
inline DB dist_sqr(Line l1, Seg l2){
    Po v0 = l1.b - l1.a, v1 = l2.a - l1.a, v2 = l2.b - l1.a; DB c1 = det(v0, v1), c2 = det(v0, v2);
    return sgn(c1) != sgn(c2) ? 0 : sqr(min(fabs(c1), fabs(c2))) / v0.length_sqr();
}

bool isIntersect(Seg l1, Seg l2){

    if (l1.a == l2.a || l1.a == l2.b || l1.b == l2.a || l1.b == l2.b) return true;

    return
        min(l1.a.x, l1.b.x) <= max(l2.a.x, l2.b.x) &&
        min(l2.a.x, l2.b.x) <= max(l1.a.x, l1.b.x) &&
        min(l1.a.y, l1.b.y) <= max(l2.a.y, l2.b.y) &&
        min(l2.a.y, l2.b.y) <= max(l1.a.y, l1.b.y) &&
    sgn( det(l1.a, l2.a, l2.b) ) * sgn( det(l1.b, l2.a, l2.b) ) <= 0 &&
    sgn( det(l2.a, l1.a, l1.b) ) * sgn( det(l2.b, l1.a, l1.b) ) <= 0;

}

inline DB dist_sqr(Seg l1, Seg l2){
    if (isIntersect(l1, l2)) return 0;
    else return min(dist_sqr(l1.a, l2), dist_sqr(l1.b, l2), dist_sqr(l2.a, l1), dist_sqr(l2.b, l1));
}

inline bool isOnSide(const Po &p, const Seg &l){
    return p == l.a || p == l.b;
}

inline bool isOnSeg(const Po &p, const Seg &l){
    return sgn(det(p, l.a, l.b)) == 0 &&
        sgn(l.a.x, p.x) * sgn(l.b.x, p.x) <= 0 && sgn(l.a.y, p.y) * sgn(l.b.y, p.y) <= 0;
}

inline bool isOnSegg(const Po &p, const Seg &l){
    return sgn(det(p, l.a, l.b)) == 0 &&
        sgn(l.a.x, p.x) * sgn(l.b.x, p.x) < 0 && sgn(l.a.y, p.y) * sgn(l.b.y, p.y) < 0;
}

inline Po intersect(const Line &l1, const Line &l2){
    return l1.a + (l1.b - l1.a) * (det(l2.a, l1.a, l2.b) / det(l2, l1));
}

// perpendicular foot
inline Po intersect(const Po & p, const Line &l){
    return intersect(Line(p, p + Po(l.a.y - l.b.y, l.b.x - l.a.x)), l);
}

inline Po rotate(Po p, DB alpha, Po o = Po()){
    p.x -= o.x, p.y -= o.y;
    return Po(p.x * cos(alpha) - p.y * sin(alpha), p.y * cos(alpha) + p.x * sin(alpha)) + o;
}

} using namespace CG;//}
//}

/** I/O Accelerator Interface .. **/ //{
template<class T> inline T& RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    return x;
}

inline char* RS(char *s){
    //gets(s);
    scanf("%s", s);
    return s;
}

int Case; template<class T> inline void OT(const T &x){
    //printf("Case %d: %d\n", ++Case, x);
    //printf("%.2lf\n", x);
    printf("%d\n", x);
    //cout << x << endl;
}
//}

//}/* .................................................................................................................................. */

const int N = 10009; // .. .

struct Po3D: Po{
    DB z;
    Po3D(DB x=0, DB y=0, DB z=0):Po(x, y),z(z){}

    friend istream& operator >>(istream& in, Po3D &p){return in >> p.x >> p.y >> p.z;}
    friend ostream& operator <<(ostream& out, Po3D p){return out << "(" << p.x << ", " << p.y << ", " << p.z << ")";}
    bool operator ==(const Po3D& r)const{return !sgn(x-r.x) && !sgn(y-r.y) && !sgn(z-r.z);};
    bool operator !=(const Po3D& r)const{return sgn(x-r.x) || sgn(y-r.y) && sgn(z-r.z);}
    Po3D operator +(const Po3D& r)const{return Po3D(x+r.x, y+r.y, z+r.z);}
    Po3D operator -(const Po3D& r)const{return Po3D(x-r.x, y-r.y, z-r.z);}
    Po3D operator *(DB k)const{return Po3D(x*k,y*k,z*k);}
    Po3D operator /(DB k)const{return Po3D(x/k,y/k,z/k);}
    DB operator *(const Po3D&)const;
    Po3D operator ^(const Po3D&)const;

    bool operator <(const Po3D &r) const{return sgn(x, r.x)<0 || !sgn(x, r.x) && (sgn(y, r.y)<0 || !sgn(y, r.y) && sgn(z, r.z)<0);}
    Po3D operator -()const{return Po3D(-x,-y,-z);}
    Po3D& operator +=(const Po3D &r){x+=r.x,y+=r.y,z+=r.z;return*this;}
    Po3D& operator -=(const Po3D &r){x-=r.x,y-=r.y,z-=r.z;return*this;}
    Po3D& operator *=(DB k){x*=k,y*=k,z*=k;return*this;}
    Po3D& operator /=(DB k){x/=k,y/=k,z/=k;return*this;}

    DB length_sqr()const{return sqr(x) + sqr(y) + sqr(z);}
    DB length()const{return sqrt(length_sqr());}
    Po unit()const{return (*this) / length();}
    bool dgt()const{return !sgn(x) && !sgn(y) && !sgn(z);}

    void input(){
        DB a, b; RF(a, b), a += 90;
        a *= PI / 180, b *= PI / 180;
        x = sin(a)*cos(b);
        y = sin(a)*sin(b);
        z = cos(a);
    }
};

inline DB dot(DB x1, DB y1, DB z1, DB x2, DB y2, DB z2){return x1*x2+y1*y2+z1*z2;}
inline DB dot(const Po3D &a, const Po3D &b){return dot(a.x,a.y,a.z,b.x,b.y, b.z);}
inline DB dot(const Po3D &p0, const Po3D &p1, const Po3D &p2){return dot(p1-p0, p2-p0);}

inline Po3D det(DB x1, DB y1, DB z1, DB x2, DB y2, DB z2){return Po3D(det(y1,z1,y2,z2),det(z1,x1,z2,x2),det(x1,y1,x2,y2));}
inline Po3D det(const Po3D &a, const Po3D &b){return det(a.x,a.y,a.z,b.x,b.y,b.z);}
inline Po3D det(const Po3D &p0, const Po3D &p1, const Po3D &p2){return det(p1-p0, p2-p0);}

inline DB box(const Po3D &a, const Po3D &b, const Po3D& c){return a*(b^c);}
inline DB box(const Po3D &p0, const Po3D &p1, const Po3D& p2, const Po3D& p3){return box(p1-p0,p2-p0,p3-p0);}

DB Po3D::operator *(const Po3D &r)const{return dot(*this, r);}
Po3D Po3D::operator ^(const Po3D &r)const{return det(*this, r);}

struct Line3D{
    Po3D a, b;
    Line3D(Po3D a = Po3D(), Po3D b = Po3D()):a(a),b(b){}
    DB length_sqr()const{return (b-a).length_sqr();}
    DB length()const{return (b-a).length();}
    DB operator *(const Line3D&)const;
    Po3D operator ^(const Line3D&)const;
};

inline DB dot(const Line3D &l1, const Line3D &l2){return dot(l1.b-l1.a, l2.b-l2.a);}
inline Po3D det(const Line3D &l1, const Line3D &l2){return det(l1.b-l1.a, l2.b-l2.a);}
DB Line3D::operator *(const Line3D &r)const{return dot(*this, r);}
Po3D Line3D::operator ^(const Line3D &r)const{return det(*this, r);}

DB f(const Line3D& a, const Line3D& b){
    return acos(fabs(a*b) / (a.length() * b.length()));
}

Po3D A[N]; Line3D l1, l2;
int n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d%d%*lf", &n, &m)){
        REP(i, n) A[i].input();
        DO(m){

            l1 = Line3D(A[RD()], A[RD()]); l2.b.input();
            DB k; RF(k), k *= RF();

            DB alpha = f(l1, l2);

            if (!sgn(alpha)) puts("0.000");
            else if (!sgn(k) || !sgn(alpha - PI/2)) puts("God Bless Him!");
            else {
                DB ans = fabs(log((1 + sin(alpha)) / (1 - sin(alpha))) / k / 2);
                printf("%.3lf\n", ans);
            }
        }

        puts("");
    }
}