Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

额,,,1985MS 真心飘过,,直接离散然后暴力过的。。。

Posted by 20107926LJW at 2012-07-24 22:50:21 on Problem 3695
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator