| ||||||||||
| 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