P2313题解

· · 题解

题面

建议加上标签“枚举，暴力”

首先，看看数据范围，500 直接暴力，也就 n^2。

对于一个点 A=(x,y)，我们枚举所有的图形：

  1. 如果这是一个矩形 (x_1,y_1,x_2,y_2)，判断 \min(x_1,x_2)<x<\max(x_1,x_2) 且 \min(y_1,y_2)<y<\max(y_1,y_2)，成立就表示 A 在这个矩形中。

  2. 如果这是一个圆，判断 A 到圆心的距离是否小于半径即可。

代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n,m,ans;
  struct node{
      char op;
      double a,b,c,d;
  }a[505];//储存所有的图形
  double x,y;
  double len(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}//求距离
  int main()
  {
      scanf("%d%d\n",&n,&m);
      for(int i=1;i<=n;i++){
          scanf("%c%lf%lf%lf",&a[i].op,&a[i].a,&a[i].b,&a[i].c);
          if(a[i].op=='r')scanf("%lf",&a[i].d);
          scanf("\n");
      }
      for(int i=1;i<=m;i++){
          scanf("%lf%lf",&x,&y);
          ans=0;
          for(int j=1;j<=n;j++){
              if(a[j].op=='r'){
                  if(min(a[j].a,a[j].c)<x&&x<max(a[j].a,a[j].c)&&min(a[j].b,a[j].d)<y&&y<max(a[j].b,a[j].d))ans++;
              }
              else{
                  if(len(x,y,a[j].a,a[j].b)<a[j].c)ans++;
              }
          }//暴力
          printf("%d\n",ans);
      }
      return 0;
  }