12882 - City Park

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12882 - City Park

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

NayaraBlack
New poster
Posts: 1
Joined: Fri Oct 14, 2016 9:12 pm

Re: 12882 - City Park

Hello guys, I'm trying to solve this problem 12882 - City Park, but I'm getting WA. I already tested the code with many test cases but all of them are correct. can you please take a look in my code and try to find the bug?(or at least give me some critical test cases)

** I'm using a plane sweep algorithm.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

struct ret{
ll lx, ly, ux, uy, id;
ret(){
lx=ly=ux=uy=id=0;
}
ret(ll a, ll b, ll c, ll d, ll f) : lx(a), ly(b), ux(c), uy(d), id(f) {}

bool operator < (ret g) const{

if(ly != g.ly) return ly < g.ly;
return uy < g.uy;
}

};

vector<ret> P;

bool compareX(ret a, ret b){

if(a.lx != b.lx) return a.lx < b.lx;
return a.ly < b.ly;
}

ll area(ret a){
return abs(a.ux - a.lx) * abs(a.uy - a.ly);
}

ll solve(){

multiset<ret> SL;//It's my plane sweep
ll ans;
ll regCont=0LL;
vector< ll > regiao, reg;
regiao.assign(P.size()+10, 0LL);
reg.assign(P.size()+10, 0LL);

for (int i = 0; i < P.size(); i++)
{
ret p = P[i];

reg[p.id] = regCont++;

if(SL.empty()){
regiao[reg[p.id]] = area(p);
SL.insert(p);
continue;
}
for(multiset<ret> :: iterator it = SL.begin(); it!=SL.end(); ){

ret b = *it;
if(b.ly > p.uy || b.uy < p.ly || b.ux < p.lx) {
multiset<ret> :: iterator tmp = it;
tmp++;
if((b.uy < p.ly && b.ux==p.lx) || b.ux < p.lx) {//when i find a rectangle that is leftside, or downside i erase it of the SL;
SL.erase(it);

it = tmp;
}else ++it;
continue;

}
if(reg[b.id] > reg[p.id]){
regiao[reg[p.id]] += regiao[reg[b.id]];
regiao[reg[b.id]] = 0LL;
b.id = p.id;
}else p.id = b.id;

++it;
}

regiao[reg[p.id]]+=area(p);
SL.insert(p);

}
ans = 0LL;
for(ll i=0LL; i<regCont; i++){

ans = max(ans, regiao[i]);
}
return ans;
}

int main(){

ll n;
ll x, y, w, h;
while(cin >> n, !cin.eof()){
ll id=0LL;
while(n--){
scanf("%lld %lld %lld %lld", &x, &y, &w, &h);
P.push_back(ret(x, y, x+w, y+h, id++));
}

sort(P.begin(), P.end(), compareX);
printf("%lld\n", solve());
P.clear();
}
}``````