Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
离散化暴力1964ms飘过~Orz#include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<cstdlib> #include<cmath> #include<vector> #define LL long long #define IT __int64 #define zero(x) fabs(x)<eps #define mm(a,b) memset(a,b,sizeof(a)) const int INF=0x7fffffff; const double inf=1e8; const double eps=1e-10; const double PI=acos(-1.0); const int Max=51; const int maxn=100001; using namespace std; typedef struct Node { int x; int y; int mark; }point; point pnt[Max]; int mark_x[Max];// int mark_y[Max]; int xx[Max]; int yy[Max]; int area[Max][Max]; bool ok[Max][Max]; bool cmp_x(point u,point v) { return u.x<v.x; } bool cmp_y(point u,point v) { return u.y<v.y; } int main() { int n,m,i,j,k,num,T,P,res; int Area; T=1; while(~scanf("%d%d",&n,&m)&&(n||m)) { for(i=1,k=0;i<=n;i++) { scanf("%d%d%d%d",&pnt[k].x,&pnt[k].y,&pnt[k+1].x,&pnt[k+1].y); pnt[k++].mark=i; pnt[k++].mark=i+n; } sort(pnt,pnt+k,cmp_x);//把x按从小到大排序 for(i=0;i<k;i++) { xx[i]=pnt[i].x; mark_x[pnt[i].mark]=i; } sort(pnt,pnt+k,cmp_y);//把y按从小到大排序 for(i=0;i<k;i++) { yy[i]=pnt[i].y; mark_y[pnt[i].mark]=i; } for(i=0;i<k-1;i++) { for(j=0;j<k-1;j++) { area[i][j]=(xx[i+1]-xx[i])*(yy[j+1]-yy[j]); } } printf("Case %d:\n",T++); P=1; while(m--) { mm(ok,false); scanf("%d",&num); while(num--) { scanf("%d",&res); for(i=mark_x[res];i<mark_x[res+n];i++)//查找第k个矩形的x { for(j=mark_y[res];j<mark_y[res+n];j++)//查找第k个矩形的y { ok[i][j]=true;//如果有重复覆盖的矩形块只会标记一次 } } } Area=0; for(i=0;i<k;i++) { for(j=0;j<k;j++) { if(ok[i][j]) Area+=area[i][j]; } } printf("Query %d: %d\n",P++,Area); } printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator