Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 643 Solved: 226
Description
汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形
和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看
起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕
竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的
任务是：在给定平面上N个图形(矩形或圆)以及M个点后，请你求出每个点在多少个矩形或圆内部(这里假设矩形的
边都平行于坐标轴)。
Input第一行为两个正整数N和M
其中N表示有多少个图形(矩形或圆)，M表示有多少个点。
接下来的N行是对每个图形的描述，
具体来说，第i+1行表示第i个图形。
先是一个字母,若该字母为“r”，则表示该图形是一个矩形,
这时后面将有4个实数x1,y1,x2,y2，表示该矩形的一对对角顶点的坐标分别为(x1,y1)和(x2,y2)；
若该字母为“c”，则表示该图形是一个圆,
这时后面将有3个实数x,y,r,表示该圆以(x,y)为圆心并以r为半径。
最后M行是对每个点的描述，其中每行将有两个实数x,y,表示一个坐标为(x,y)的点。
Output包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部
(当某点在一个图形的边界上时，我们认为该点不在这个图形的内部)。
Sample Input3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000
1
2
0
1
/**************************************************************
Problem: 1199
User: ictsing
Language: C++
Result: Accepted
Time:5380 ms
Memory:20828 kb
****************************************************************/
//BZOJ1199 [HNOI2005]汤姆的游戏
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char op[10];
int totr=0,totc=0;
const int mt = 250000+5;
struct qwq{
double x1,x2,y1,y2;
}r[mt];
struct ovo{
double x,y,r;
}c[mt];
struct node{
double x,y;
int id;
}n[mt];
int ans[mt];
bool cmp(node a,node b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double dis(node a,ovo b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int main()
{
int n_=read(),m=read();
for(int i=1;i<=n_;i++)
{
scanf("%s",op);
if(op[0]=='r')
{
double a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
r[++totr].x1=min(a,c);
r[totr].y1=min(b,d);
r[totr].x2=max(a,c);
r[totr].y2=max(b,d);
}
else
{
scanf("%lf",&c[++totc].x);
scanf("%lf",&c[totc].y);
scanf("%lf",&c[totc].r);
}
}
for(int i=1;i<=m;i++)
{
scanf("%lf%lf",&n[i].x,&n[i].y),n[i].id=i;
}
sort(n+1,n+m+1,cmp);
for(int i=1;i<=totr;i++)
{
int lft=upper_bound(n+1,n+m+1,(node){r[i].x1,0.0,0},cmp)-n;
int rgt=lower_bound(n+1,n+m+1,(node){r[i].x2,0.0,0},cmp)-n-1;
for(int j=lft;j<=rgt;j++)
{
if(n[j].x>r[i].x1&&n[j].x<r[i].x2&&n[j].y<r[i].y2&&r[i].y1<n[j].y)
ans[n[j].id]++;
}
}
for(int i=1;i<=totc;i++)
{
int lft=upper_bound(n+1,n+m+1,(node){c[i].x-c[i].r,0.0,0},cmp)-n;
int rgt=lower_bound(n+1,n+m+1,(node){c[i].x+c[i].r,0.0,0},cmp)-n-1;
for(int j=lft;j<=rgt;j++)
{
if(dis(n[j],c[i])<c[i].r*c[i].r)
ans[n[j].id]++;
}
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
评论