Description

小雪和小可可被困在了一個(gè)無限大的迷宮中。

已經(jīng)知道這個(gè)迷宮有 N 堵環(huán)狀的墻，如果把整個(gè)迷宮看作是一個(gè)二維平面，那么每一堵墻都是平面上一個(gè)圓。任意兩個(gè)圓不相交，不重合，也不會(huì)相切， 但有可能相互包含。小雪和小可可分別被困在了 2 個(gè)不同的位置，且保證他們的位置與這些圓不重合。

他們只有破壞墻面才能穿過去。

小雪希望知道，如果他們要相見，至少要破壞掉多少堵墻？他們可以在任何位置相見。

Input

第一行有一個(gè)整數(shù) N，表示有多少堵墻，保證 0<=N<=8000。

之后 N 行，每一行有三個(gè)整數(shù) x， y 和 r，表示有一堵環(huán)狀的墻是以(x,y)為圓形， r為半徑的。保證-100000000<=x,y,r<=100000000。

再下一行有一個(gè)整數(shù) Q，表示有多少組詢問，保證 1<=Q<=8000。

之后 Q 行，每一行有 4 個(gè)整數(shù) a， b， c 和 d，給出了一組詢問，表示小雪所在的位置為(a,b)，小可可所在的位置為(c,d)。保證-100000000<=a,b,c,d<=100000000。

Output

輸出 Q 行，對應(yīng) Q 次詢問，每一行輸出一個(gè)整數(shù)，表示最小需要破壞掉多少堵墻才能相見。

Sample Input

3
0 0 1
3 0 1
2 0 4
1
0 0 3 0

Sample Output

2

Hint

對于 20%的數(shù)據(jù)， 0<=N<=200。

對于 40%的數(shù)據(jù)， 0<=N<=1000。

對于 100%的數(shù)據(jù)， 0<=N<=8000， 0<=Q<=8000。

此外，還有額外的 20%的數(shù)據(jù)，滿足 0<=N<=1000， 0<=Q<=1000。

所有數(shù)絕對值不超過 100000000。

大數(shù)據(jù)點(diǎn)時(shí)限3s。

?

題解

水題一道...枚舉所有的圓看是否同在園內(nèi)或同在圓外...

1 //It is made by Awson on 2017.11.6 2 #include <map> 3 #include <set> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <cstdio> 9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define sqr(x) ((x)*(x)) 19 #define y1 yy 20 using namespace std; 21 const int N = 8000; 22 23 int n, m; 24 struct circle { 25 LL x ,y, r; 26 }a[N+5]; 27 LL x1, x2, y1, y2; 28 29 void work() { 30 scanf("%d", &n); 31 for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].r); 32 scanf("%d", &m); 33 while (m--) { 34 int cnt = 0; bool flag = 0; 35 scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2); 36 for (int i = 1; i <= n; i++) { 37 flag = 0; 38 if (sqr(x1-a[i].x)+sqr(y1-a[i].y) < sqr(a[i].r)) flag = !flag; 39 if (sqr(x2-a[i].x)+sqr(y2-a[i].y) < sqr(a[i].r)) flag = !flag; 40 cnt += flag; 41 } 42 printf("%d\n", cnt); 43 } 44 } 45 int main() { 46 work(); 47 return 0; 48 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/NaVi-Awson/p/7857303.html

總結(jié)

以上是生活随笔為你收集整理的[AHOI 2016初中组]迷宫的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。