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 |
苯质上是个H2O题,贪心,能切就切,一堆STL都0ms#include <iostream> #include <vector> #include <stdio.h> #include <algorithm> using namespace std; int xIdx[40004], yIdx[40004]; int xfen[200], yfen[200]; struct intv{ int start, end; intv(int s, int e): start(s), end(e){} }; ostream& operator<<(ostream& o, const intv& i){ o << '[' << i.start << "," << i.end << ']'; return o; } vector<intv> xIntvs[200], yIntvs[200]; int maxArea(int x1, int y1, int x2, int y2){ int minxIdx = xIdx[x1] + 1, maxxIdx = xIdx[x2] - 1; for(int i = minxIdx; i <= maxxIdx; i++){ int sz = xIntvs[i].size(); for(int j = 0; j < sz; j++){ if(xIntvs[i][j].start <= y1 && xIntvs[i][j].end >= y2){ int mx1 = maxArea(x1, y1, xfen[i], y2); int mx2 = maxArea(xfen[i], y1, x2, y2); return (mx1 > mx2) ? mx1 : mx2; } } } int minyIdx = yIdx[y1] + 1, maxyIdx = yIdx[y2] - 1; for(int i = minyIdx; i <= maxyIdx; i++){ int sz = yIntvs[i].size(); for(int j = 0; j < sz; j++){ if(yIntvs[i][j].start <= x1 && yIntvs[i][j].end >= x2){ int mx1 = maxArea(x1, y1, x2, yfen[i]); int mx2 = maxArea(x1, yfen[i], x2, y2); return (mx1 > mx2) ? mx1 : mx2; } } } return (x2-x1) * (y2-y1); } bool compare(const intv &i1, const intv &i2){ return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end); } int main() { int T; scanf("%d", &T); for(int ii = 0; ii < T; ii++){ int mnX = 2147483647, mnY = 2147483647; int x, y; scanf("%d%d", &x, &y); int xl[110], yl[110], xh[110], yh[110]; int gs; scanf("%d", &gs); for(int i = 0; i < gs; i++){ scanf("%d%d%d%d", &xl[i], &yl[i], &xh[i], &yh[i]); if(xl[i] < mnX) mnX = xl[i]; if(yl[i] < mnY) mnY = yl[i]; } for(int i = 0; i < gs; i++){ xl[i] -= mnX, yl[i] -= mnY, xh[i] -= mnX, yh[i] -= mnY; } int mxX = x, mxY = y; bool xUsed[40004] = {0}, yUsed[40004] = {0}; int xgs = 0, ygs = 0; for(int i = 0; i < gs; i++){ if(xl[i] != 0 && xUsed[xl[i]]==0){ xUsed[xl[i]] = 1; xfen[xgs] = xl[i]; //xIdx[xl[i]] = xgs; xgs++; } if(xh[i] != mxX && xUsed[xh[i]] == 0){ xUsed[xh[i]] = 1; xfen[xgs] = xh[i]; //xIdx[xh[i]] = xgs; xgs++; } if(yl[i] != 0 && yUsed[yl[i]] == 0){ yUsed[yl[i]] = 1; yfen[ygs] = yl[i]; //yIdx[yl[i]] = ygs; ygs++; } if(yh[i] != mxY && yUsed[yh[i]]==0){ yUsed[yh[i]] = 1; yfen[ygs] = yh[i]; //yIdx[yh[i]] = ygs; ygs++; } } sort(xfen, xfen+xgs); sort(yfen, yfen+ygs); for(int i = 0; i < xgs; i++) xIdx[xfen[i]] = i; for(int j = 0; j < ygs; j++) yIdx[yfen[j]] = j; xIdx[0] = yIdx[0] = -1; xIdx[mxX] = xgs, yIdx[mxY] = ygs; vector<intv> xintvs[200], yintvs[200]; for(int i = 0; i < gs; i++){ int x1 = xl[i], x2 = xh[i], y1 = yl[i], y2 = yh[i]; if(x1 != 0){ xintvs[xIdx[x1]].push_back(intv(y1, y2)); } if(x2 != mxX){ xintvs[xIdx[x2]].push_back(intv(y1, y2)); } if(y1 != 0){ yintvs[yIdx[y1]].push_back(intv(x1, x2)); } if(y2 != mxY){ yintvs[yIdx[y2]].push_back(intv(x1, x2)); } } for(int i = 0; i < xgs; i++) sort(xintvs[i].begin(), xintvs[i].end(), compare); for(int j = 0; j < ygs; j++) sort(yintvs[j].begin(), yintvs[j].end(), compare); for(int i = 0; i < xgs; i++) xIntvs[i].clear(); for(int j = 0; j < ygs; j++) yIntvs[j].clear(); for(int i = 0; i < xgs; i++){ //vector<intv> &temp = xintvs[i]; int sz = xintvs[i].size(); int ks = xintvs[i][0].start; int js = xintvs[i][0].end; for(int j = 0; j < sz; j++){ if(j == sz-1 || xintvs[i][j+1].start > js){ xIntvs[i].push_back(intv(ks, js)); if(j != sz-1){ ks = xintvs[i][j+1].start; js = xintvs[i][j+1].end; } } else{ if(xintvs[i][j+1].end > js) js = xintvs[i][j+1].end; } } } for(int i = 0; i < ygs; i++){ //vector<intv> &temp = yintvs[i]; int sz = yintvs[i].size(); int ks = yintvs[i][0].start; int js = yintvs[i][0].end; for(int j = 0; j < sz; j++){ if(j == sz-1 || yintvs[i][j+1].start > js){ yIntvs[i].push_back(intv(ks,js)); if(j != sz-1){ ks = yintvs[i][j+1].start; js = yintvs[i][j+1].end; } } else{ if(yintvs[i][j+1].end > js) js = yintvs[i][j+1].end; } } } int mA = maxArea(0, 0, mxX, mxY); printf("%d\n", mA); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator