2 条题解
-
0
#include<bits/stdc++.h> using namespace std; struct node { int x1,y1,x2,y2; }a[10005]; struct point { int x,y,w; }p[20005]; bool cmp(point n1,point n2) { return n1.x<n2.x; } int find(int l,int r,int x) { int ans=r+1,mid; while(l<=r) { mid=(l+r)/2; if(p[mid].x>=x){ans=mid;r=mid-1;} else l=mid+1; } return ans; } int find2(int l,int r,int x) { int ans=l-1,mid; while(l<=r) { mid=(l+r)/2; if(p[mid].x<=x){ans=mid;l=mid+1;} else r=mid-1; } return ans; } int s[20005]; int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); if(a[i].x1>a[i].x2)swap(a[i].x1,a[i].x2); if(a[i].y1>a[i].y2)swap(a[i].y1,a[i].y2); } for(int i=1;i<=m;i++) { scanf("%d%d",&p[i].x,&p[i].y); p[i].w=i; } sort(p+1,p+m+1,cmp); for(int i=1;i<=n;i++) { int l=find(1,m,a[i].x1),r=find2(1,m,a[i].x2),ans=0; for(int j=l;j<=r;j++)if(a[i].y1<=p[j].y&&p[j].y<=a[i].y2)s[p[j].w]++; } for(int i=1;i<=m;i++)printf("%d\n",s[i]); return 0; } -
0
#include<bits/stdc++.h> using namespace std; struct node { int x1,y1,x2,y2; }a[10005]; struct point { int x,y,w; }p[20005]; bool cmp(point n1,point n2) { return n1.x<n2.x; } int find(int l,int r,int x) { int ans=r+1,mid; while(l<=r) { mid=(l+r)/2; if(p[mid].x>=x){ans=mid;r=mid-1;} else l=mid+1; } return ans; } int find2(int l,int r,int x) { int ans=l-1,mid; while(l<=r) { mid=(l+r)/2; if(p[mid].x<=x){ans=mid;l=mid+1;} else r=mid-1; } return ans; } int s[20005]; int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); if(a[i].x1>a[i].x2)swap(a[i].x1,a[i].x2); if(a[i].y1>a[i].y2)swap(a[i].y1,a[i].y2); } for(int i=1;i<=m;i++) { scanf("%d%d",&p[i].x,&p[i].y); p[i].w=i; } sort(p+1,p+m+1,cmp); for(int i=1;i<=n;i++) { int l=find(1,m,a[i].x1),r=find2(1,m,a[i].x2),ans=0; for(int j=l;j<=r;j++)if(a[i].y1<=p[j].y&&p[j].y<=a[i].y2)s[p[j].w]++; } for(int i=1;i<=m;i++)printf("%d\n",s[i]); return 0; }
- 1
信息
- ID
- 791
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 2
- 标签
- 递交数
- 25
- 已通过
- 20
- 上传者