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