Page 1 of 2

10043 - Chainsaw Massacre

Posted: Thu Feb 28, 2002 8:17 pm
by Cloud
Help me plz :sad:

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

Posted: Fri Mar 01, 2002 4:04 am
by shahriar_manzoor
Send me a mail with your code attached.
address: shahriar@neksus.com

10043 Chainsaw massacre No idea please help....

Posted: Wed Nov 27, 2002 3:55 pm
by jaivasanth
I have no idea as to how to go about solving this problem...
Is there a DP soln... please explain.....

Posted: Wed Nov 27, 2002 10:32 pm
by arnsfelt
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

thanx...

Posted: Mon Dec 02, 2002 9:20 am
by jaivasanth
Thanx.. i was able to figure out the code...

Incorrect testdata?

Posted: Sun Dec 15, 2002 11:55 am
by Nak
I think the testdata in this problem is incorrect :-(

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

Posted: Sat Feb 08, 2003 2:39 am
by GigS
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.

Posted: Mon Feb 23, 2004 11:11 am
by junbin
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

Posted: Sat May 08, 2004 10:50 pm
by technobug
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]

Posted: Fri Nov 12, 2004 7:08 pm
by d91-lek
This is a problem:

Code: Select all

2
5 2
1 2 1
0
5 2
1 3 1
0
Answer:

Code: Select all

6
6
Whereas your code gives:

Code: Select all

6
5

Posted: Sun May 06, 2007 7:13 am
by xavier_lt
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

Posted: Mon May 07, 2007 3:40 am
by xavier_lt
Left edge is the left border of the forest.
i haven't noticed that .... ac now....

10043 - Chainsaw Massacre WA???

Posted: Mon May 05, 2014 11:19 pm
by mack_attack
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

Re: 10043 - Chainsaw Massacre WA???

Posted: Wed May 07, 2014 9:22 pm
by brianfry713

Re: 10043 - Chainsaw Massacre WA???

Posted: Wed May 07, 2014 9:57 pm
by mack_attack
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.