| ||||||||||
| 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 | |||||||||
直接暴力过呀~才32ms#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator