| ||||||||||
| 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