## 10043 - Chainsaw Massacre

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

Moderator: Board moderators

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

### 10043 - Chainsaw Massacre

Help me plz

Code: Select all

``````/* @JUDGE_ID: xxxxx 10043 C++ */
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define maxn 5000

typedef int (*fptr)(const void*, const void*);

struct point {
int x,y;
} p[maxn];

int cmp(point *a,point *b) {
return (*a).x - (*b).x;
}

int n,i,j,k;
int l,w,u,v;
int num;

void add(int xx,int yy) {
p[n].x = xx, p[n++].y = yy;
p[n].x = xx, p[n++].y = 0;
p[n].x = xx, p[n++].y = w;
p[n].x = 0, p[n++].y = yy;
p[n].x = l, p[n++].y = yy;
}

int main() {
cin >> num;
while (num--) {
cin >> l >> w;
n = 4;
p[0].x = 0, p[0].y = 0;
p[1].x = l, p[1].y = 0;
p[2].x = 0, p[2].y = w;
p[3].x = l, p[3].y = w;
while (cin >> k) {
if (k == 0) break;
cin >> u >> v;
int dx = 0, dy = 0;
if (k > 1) cin >> dx >> dy;
for (i = 0; i < k; i++) add(u,v), u += dx, v += dy;
}
qsort((void *)p,n,sizeof(p[0]),(fptr)cmp);
int maxs = 0;
for (i = 0; i < n; i++) {
int u = w, d = 0, j = i;
int found;
while (j < n - 1) {
found = 0;
while (++j) {
if (p[i].x < p[j].x) {
if (p[i].y >= p[j].y && p[j].y >= d) found = 1;
if (p[i].y <= p[j].y && p[j].y <= u) found = 2;
}
if (found || j == n - 1) break;
}
int tmp = (p[j].x - p[i].x) * (u - d);
maxs = maxs > tmp ? maxs : tmp;
if (found == 1) d = p[j].y;
if (found == 2) u = p[j].y;
}
}
cout << maxs << endl;
}
return 0;
}``````

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
Send me a mail with your code attached.

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

I have no idea as to how to go about solving this problem...
Is there a DP soln... please explain.....

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
No, DP doesn't lead to a good solution.
Instead, a sweep-style algorithm is needed.
Aim at an O(n^2) time algorithm.

WARNING: Spoiler follows:

Consider the largest empty rectangle.
There are two cases:
1) Left edge is the left border of the forest.
2) There is a tree on the left edge.

Case 1 is a special case to be handled seperately.

Now for case 2:
For each point we perform a sweep.
During the sweep we maintain two y-coordinates representing
the upper and lower edge of the optimal rectangle having the first point
on the left edge and the current point on the right edge.

Now, only thing left is to handle case 1) and to figure out how to update

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

### thanx...

Thanx.. i was able to figure out the code...

Nak
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

### Incorrect testdata?

I think the testdata in this problem is incorrect

My assert(n_trees <= 1000); fails, without it i get accepted.

GigS
New poster
Posts: 2
Joined: Sat Feb 08, 2003 2:34 am
you must use bigger array ( 5050 should be ok ;) in that version.

but really you need only that points :

p[n].x = xx, p[n++].y = yy;
p[n].x = 0, p[n++].y = yy;

so array can be 2020

If you add all five points, you will get time limit exceeded.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
I think it should be noted that there are definitely MORE than 1000 trees. In fact, if I set my program's limit to 1000 trees, it gives WA. When I changed it to 5000 trees, I get AC.

I doubt you need 5000 trees, probably 2000 will do, but I'm too lazy to keep trying. :p

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
i tried to do this sweep with all points including (0,0) in order to check for a border on the left side of our map.... though i keep on WA.... any test cases? tips? advices? code help?

the algo is (kinda) exactly what was described.... but I surely missed something

[cpp]#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int l,w;

vector<int*> p;
int pc;
int m;

void area(int p1, int x1, int y1, int p2, int y2) {

// cout << "new call: " << p1 << " and " << p2;
// cout << "\t\t(" << x1 << "," << y1 << ")\t(" << p[p2][0] << "," << y2 << ")" << endl;

int pn = p2 + 1;
while(pn!=pc && (p[pn][0]<p[p2][0] || p[pn][1]>y2 || p[pn][1]<y1)) {
pn++;
}

if(pn==pc) {
// so i got to the right border
int area1 = (l - x1) * (y2 - y1);
// cout << "right border area: " << area1 <<endl;
if(area1>m) {
m = area1;
}
return;
}

//cout << "next point at my right side: " << p[pn][0] << "," << p[pn][1] << endl;

// lets test if this area is bigger than the previous ones
int area1 = (y2 - y1) * (x1 - p[pn][0]);
if(area1>m) {
m = area1;
// cout << x1 <<","<<y1 << " e " << p[pn][0] << ","<<y2<<":" << area1 << endl;
}

if((p[pn][1] - y1) * (l-x1) > m) {
// this point will be my uppermost border
area(p1,x1,y1,pn,p[pn][1]);
}

if((y2 - p[pn][1]) * (l-x1) > m) {
// this point will be my bottom
area(p1,x1,p[pn][1],pn,y2);
}

}

bool ordena(const int *i1, const int *i2) {
return i1[0] < i2[0];
}

void executa() {

// if there are no points, its nice
if(pc==0) { cout << (l*w) << endl; return; }

/* cout << l << " x " << w << endl;
cout << pc << " trees"<< endl;*/

m = 0;

// adds a new point at 0,0
int iz[2];
iz[0] = 0;
iz[1] = 0;
p.push_back(iz);
pc++;

sort(p.begin(),p.end(),ordena);

// for(int i=0;i!=pc;i++) {
// cout << "tree #" << (i+1) <<": (" <<p[0] << "," << p[1] << ")"<<endl;
// }

int i,i2;
for(int i=0;i!=pc;i++) {
if(i!=0 && p[0]==p[i-1][0]) continue;
// cout << "\n\n\nstarting with tree number " << (i+1) << endl;
area(i,p[0],0,i,w);
}

cout << m << endl;
}

int main() {

int c,k,bx,by,dx,dy;
cin >> c;
while(c--!=0) {
pc = 0;
cin >> l >> w;
p.clear();
while(true) {
cin >> k;
if(k==0) break;
if(k==1) {
int *k = new int[2];
cin >> k[0] >> k[1];
if(k[0]==0 || k[0]==l || k[1]==0 || k[1]==w) continue;
p.push_back(k);
pc++;
continue;
}
cin >> bx >> by >> dx>>dy;
bx -= dx; by -= dy;
while(k--!=0) {
int *k = new int[2];
k[0] = (bx += dx);
k[1] = (by += dy);
if(k[0]==0 || k[0]==l || k[1]==0 || k[1]==w) continue;
p.push_back(k);
pc++;
}
}
executa();
}

}[/cpp]

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:
This is a problem:

Code: Select all

``````2
5 2
1 2 1
0
5 2
1 3 1
0
``````

Code: Select all

``````6
6
``````
Whereas your code gives:

Code: Select all

``````6
5
``````

xavier_lt
New poster
Posts: 2
Joined: Sun May 06, 2007 7:06 am
could anybody give me more test datas ? I cannot get through this problem. here is my code : ( sorry for my poor english. )

Code: Select all

``````code deleted
``````
Last edited by xavier_lt on Mon May 07, 2007 3:40 am, edited 1 time in total.

xavier_lt
New poster
Posts: 2
Joined: Sun May 06, 2007 7:06 am
Left edge is the left border of the forest.
i haven't noticed that .... ac now....

mack_attack
New poster
Posts: 3
Joined: Mon May 05, 2014 11:10 pm

### 10043 - Chainsaw Massacre WA???

Hi All

I keep getting WA when I try to submit an answer to 10043.
I've tested with the example input and I get the expected output, I even created a few more myself and always get the right answer.

I also noticed that my initial code that expected no more than 1000 trees (like the puzzle states) kept getting a Runtime Error.
I increased it to 2048 (too be safe) and now it runs but gets WA and I dont no why.

So wondering if the format of the input data is different from the specified one on the puzzle.

Any suggestions or extra test data?

Thanks

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

### Re: 10043 - Chainsaw Massacre WA???

Check input and AC output for thousands of problems on uDebug!

mack_attack
New poster
Posts: 3
Joined: Mon May 05, 2014 11:10 pm

### Re: 10043 - Chainsaw Massacre WA???

I looked at that post, I tried increasing my maximum tree count which just stopped me from getting Runtime error and took me to the Wrong Answer stage, and I tried the test data they gave with mine and it worked. There must be a special edge case that my solution doesn't work for.

I've tried, empty paddock, paddock with only trees on the borders, paddock with 1 tree, random generated paddock, paddock with the largest area completely enclosed with trees.

Its always returns the expected result. I can't think of any other cases could fail on.