12882 - City Park

All about problems in Volume 128. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

12882 - City Park

Post by brianfry713 »

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

Post by NayaraBlack »

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();
	}
}
Please someone help me!
Post Reply

Return to “Volume 128 (12800-12899)”