| ||||||||||
| 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 | |||||||||
额,,,1985MS 真心飘过,,直接离散然后暴力过的。。。#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef struct aaa{
int x ,y ,id;
}POINT;
POINT pnt [50];
int idx [50] ,idy[50] ;
int xx[50];
bool flag[50][50];
int area[50][50];
bool cmpx (POINT A ,POINT B){
return A.x < B.x ;
}
bool cmpy (POINT A ,POINT B){
return A.y < B.y;
}
int main() {
int i ,j ,k ,l ,n ,m ,tt = 1 ,a ,t ,ans;
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].id = i;
pnt [k +1].id = i + n;
k += 2;
}
sort (pnt ,pnt + 2*n ,cmpx);
for (i = 0;i < k ;i ++){
xx[i] = pnt[i].x;
idx[pnt[i].id] = i;
}
sort (pnt ,pnt + 2*n ,cmpy);
for (i = 0;i < k ;i ++) idy[pnt[i].id] = i;
for (i = 0 ; i < k ; i ++)
for (j = 0 ;j < k ; j ++)
area[i][j] = (xx[i+1]-xx[i]) * (pnt[j+1].y - pnt[j].y); //这个地方预处理才能飘过,否则每次计算直接TLE - -!
printf ("Case %d:\n",tt++);
for (l = 1 ; l <= m ;l ++){
memset (flag , 0 ,sizeof (flag));
scanf("%d" ,&t);
while (t--) {
scanf("%d", &a);
// printf ("cur a= %d ,idx =%d ,idx n =%d ,idy =%d ,idy n =%d \n",a, idx[a], idx[a+n] , idy[a] , idy[a+n]);
for (i = idx[a] ; i < idx[a+n] ; i ++)
for (j = idy[a] ; j < idy[a+n] ; j ++)
flag [i][j] =true;
}
ans = 0;
for (i = 0 ; i < k ; i ++)
for (j = 0 ;j < k ; j ++)
if (flag[i][j])
ans += area[i][j];
printf ("Query %d: %d\n",l ,ans);
}
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