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