Post
by **technobug** » Sat May 08, 2004 10:50 pm

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]