### 10043 - Chainsaw Massacre

Posted:

**Thu Feb 28, 2002 8:17 pm**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;
}
```