12882 - City Park
Moderator: Board moderators
-
- 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!
-
- 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.
Please someone help me!
** 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();
}
}