[AHOI 2016初中组]迷宫-白红宇

[AHOI 2016初中组]迷宫

阅读量：5098 次

发布时间：2019-06-13

本文共 1896 字，大约阅读时间需要 6 分钟。

Description

小雪和小可可被困在了一个无限大的迷宫中。

已经知道这个迷宫有 N 堵环状的墙，如果把整个迷宫看作是一个二维平面，那么每一堵墙都是平面上一个圆。任意两个圆不相交，不重合，也不会相切，但有可能相互包含。小雪和小可可分别被困在了 2 个不同的位置，且保证他们的位置与这些圆不重合。

他们只有破坏墙面才能穿过去。

小雪希望知道，如果他们要相见，至少要破坏掉多少堵墙？他们可以在任何位置相见。

Input

第一行有一个整数 N，表示有多少堵墙，保证 0<=N<=8000。

之后 N 行，每一行有三个整数 x， y 和 r，表示有一堵环状的墙是以(x,y)为圆形， r为半径的。保证-100000000<=x,y,r<=100000000。

再下一行有一个整数 Q，表示有多少组询问，保证 1<=Q<=8000。

之后 Q 行，每一行有 4 个整数 a， b， c 和 d，给出了一组询问，表示小雪所在的位置为(a,b)，小可可所在的位置为(c,d)。保证-100000000<=a,b,c,d<=100000000。

Output

输出 Q 行，对应 Q 次询问，每一行输出一个整数，表示最小需要破坏掉多少堵墙才能相见。

Sample Input

0 0 1

3 0 1

2 0 4

0 0 3 0

Sample Output

Hint

对于 20%的数据， 0<=N<=200。

对于 40%的数据， 0<=N<=1000。

对于 100%的数据， 0<=N<=8000， 0<=Q<=8000。

此外，还有额外的 20%的数据，满足 0<=N<=1000， 0<=Q<=1000。

所有数绝对值不超过 100000000。

大数据点时限3s。

题解

水题一道...枚举所有的圆看是否同在园内或同在圆外...

1 //It is made by Awson on 2017.11.6 2 #include  3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define LL long long16 #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 yy20 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 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7857303.html

你可能感兴趣的文章