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

直接暴力过呀~才32ms

Posted by KatrineYang at 2016-12-02 13:36:04 on Problem 1389
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <set>
#include <algorithm>
using namespace std;

int cnt, xCnt, yCnt;

void sw(int &x1, int &x2){
	int tmp = x1;
	x1 = x2;
	x2 = tmp;
}

struct rect{
	int x1,y1,x2,y2;
}rects[1024], nrects[1024];

int xPlc[2048], yPlc[2048];
int nxPlc[50005], nyPlc[50005];

bool cmpT(const rect& r1, const rect& r2){
	return r1.x1 < r2.x1;
}

bool cmpW(const rect& r1, const rect& r2){
	return r1.x2 < r2.x2;
}

int main() {
	while(1){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1==-1 && y1==-1 && x2==-1 && y2==-1) break;
		cnt = 0;
		while(1){
			if(x1 > x2) sw(x1, x2);
			if(y1 > y2) sw(y1, y2);
			rects[cnt].x1 = x1, rects[cnt].x2 = x2, rects[cnt].y1 = y1, rects[cnt].y2 = y2;
			cnt++;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if(x1==-1 && y1==-1 && x2==-1 && y2==-1) break;
		}
		set<int>xs, ys;
		for(int i = 0; i < cnt; i++){
			xs.insert(rects[i].x1);
			xs.insert(rects[i].x2);
			ys.insert(rects[i].y1);
			ys.insert(rects[i].y2);
		}
		xCnt = yCnt = 0;
		for(set<int>::iterator it = xs.begin(); it != xs.end(); it++){
			xPlc[xCnt] = *it;
			nxPlc[*it] = xCnt;
			xCnt++;
		}
		for(set<int>::iterator it = ys.begin(); it != ys.end(); it++){
			yPlc[yCnt] = *it;
			nyPlc[*it] = yCnt;
			yCnt++;
		}
		for(int i = 0; i < cnt; i++) nrects[i] = rects[i];
		sort(rects, rects+cnt, cmpT);
		sort(nrects, nrects+cnt, cmpW);
		long long int area = 0;
		int cs[2048] = {0};
		int curLen = 0;
		int pos = 0, nPos = 0;
		for(int i = 0; i < xCnt-1; i++){
			while(nrects[nPos].x2 == xPlc[i]){
				for(int j = nyPlc[nrects[nPos].y1]; j < nyPlc[nrects[nPos].y2]; j++){
					cs[j]--;
					if(cs[j]==0) curLen -= (yPlc[j+1]-yPlc[j]);
				}
				nPos++;
			}
			while(rects[pos].x1 == xPlc[i]){
				for(int j = nyPlc[rects[pos].y1]; j < nyPlc[rects[pos].y2]; j++){
					cs[j]++;
					if(cs[j]==1) curLen += (yPlc[j+1]-yPlc[j]);
				}
				pos++;
			}
			area += ((long long int)curLen) * (xPlc[i+1]-xPlc[i]);
		}
		printf("%I64d\n", area);
	}
	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