149 - Forests

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

Moderator: Board moderators

Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm
I am trying to solve this program in this way:
to get the first Quadrant number,
then rotates the entire map 90 degrees
and so on.
In this way I get the total number;
But unlucky I cannot pass almost test input! even the sample input given
by the program.
Here is my code.
Can someone give me some suggestion?

Code: Select all

The code has been deleted!
Because I have a stupid fault!
I find it after I draw this problem in the paper!!!

Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm
Here is my new code:
At this time it can pass most sample inputs that I can find in this website!
Such as:
0.5 0.5 0.5 -> 4
0.1 0.4 0.6 -> 134
0.1 0.5 0.5 -> 132
0.43 0.5 0.5 -> 12
0.25 0.25 0.33 -> 24
0.15 0.18 0.46 ->58
but I cannot get correct output when the input is :
0.15 0.16 0.19 -> 62
0.125 0.46 0.5 -> 84
even the sample input that this problem provide:
0.10 0.46 0.38 -> 129

Below is my new code.
I'm looking for your help, plz!

Code: Select all

#include <iostream.h>
#include <math.h>

const double PI = 2*acos(0);
const double MINGAP = PI/18000;
const double EPS = 1e-9;

struct AngleRange
{
double from;
double to;

AngleRange* next;
};
AngleRange* head = NULL;
AngleRange* end = NULL;
struct POINT
{
double x;
double y;
};

AngleRange* getAngleRange(POINT observer, POINT p, double& range)
{
AngleRange* ar = new AngleRange;

double dist = sqrt((observer.y-p.y)*(observer.y-p.y)+(observer.x-p.x)*(observer.x-p.x));
double center = atan2(p.y-observer.y, p.x-observer.x);
ar->from = center - range;
ar->to = center + range;
range *= 36000;
return ar;
}

{
{
}
else
{
end->next = ar;
}
end = ar;
ar->next = NULL;
}

int isObscure(AngleRange* ar)
{
double a, b, c, d;
AngleRange* p;
a = ar->from;
b = ar->to;
for (p=head; p!=NULL; p=p->next)
{
c = p->from;
d = p->to;
if ((a-d>EPS)||(c-b>EPS))
continue;
p->from = (c-a>EPS)?a:c;
p->to = (b-d>EPS)?b:d;
return 1;
}

return 0;
}

{
int i, j;
int num = 0;
POINT tmp;
AngleRange* ar;
double range;

head = end = NULL;

for (i=1; ; i++)
{
for (j=1; ; j++)
{
tmp.x = j;
tmp.y = i;
ar = getAngleRange(observer, tmp, range);
if ((PI-range>EPS)||(fabs(range-PI)<EPS))
{
delete ar;
break;
}
if (range>PI)
{
if (isObscure(ar)<1)
{
num++;
}
else
{
delete ar;
}
}
else
{
delete ar;
break;
}
}
if (j==1)
break;
}

AngleRange* p;
AngleRange* pN;
for (p=head; p!=NULL; p=pN)
{
pN = p->next;
delete p;
}

return num;
}

int main()
{
double diameter;
POINT tmp;
double x, y;
int num;

while (1)
{
cin>>diameter>>x>>y;
if ((diameter==0)&&(x==0)&&(y==0))
break;
num = 0;
tmp.x = x;
tmp.y = y;
tmp.x = 1-y;
tmp.y = x;
tmp.x = 1-x;
tmp.y = 1-y;
tmp.x = y;
tmp.y = 1-x;

cout<<num<<endl;
}

return 0;
}
SOS!
Help!
Help!
Help!!!

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
I changed the following in your code, and it now passes all the sample input on the board, plus the sample input from the problem. This should take care of the 0.01 degrees gap mentioned in the problem description.

Code: Select all

AngleRange* getAngleRange(POINT observer, POINT p, double& range)
{
AngleRange* ar = new AngleRange;

double dist = sqrt((observer.y-p.y)*(observer.y-p.y)+(observer.x-p.x)*(observer.x-p.x));
double center = atan2(p.y-observer.y, p.x-observer.x);
ar->from = center - range - (0.005*PI/180);   // changed
ar->to = center + range + (0.005*PI/180);     // changed
range *= 36000;
return ar;
}
However, your program is slow, and it might get TLE... I also had to make massive (non-algorithmic) changes to get it to compile under GNU C++.

While on the subject, I have WA on this problem. Could anyone with AC give me the output to these cases:

Code: Select all

0.10 0.10 0.10
0.20 0.20 0.80
My program outputs 122 and 34, but I'm not sure if my answers are correct. The above program outputs 124 and 34, and according to some other i/o data I have, the answers could be 92 and 28...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
I finally got AC for this problem. It turns out I did a stupid trigonometry mistake that only gave differing answers when the viewer was very close to a tree.

By the way, the correct answers to the last two test cases are 124 and 34.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

149

Can any one please help me to solve this problem?
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Are you getting WA or you just don't know how to solve it?

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
well... i thought in this way:

first dividing the co-ordinate into 4 sections.

for each section:

find the maximum possible distance for a point. then gather the points which is < max_dist inside maxdist*maxdist square. then sort them by distance.

then from lower distance to higher, find its range and see if it overlaps with anyother ranges before. and thus update.

i used lower_bound() to make searching of range lgn and thus inserting the new element so that the vector is always sorted.

Now i don't know whther this is the correct way or not, but actually my code is getting tle in my own machine.
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Self judging is the best judging!

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am
I also have trouble with that problem. I don't know how to do it...

You're never too old to become younger...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I've got accepted with this simple algorithm.
I find the number of trees in each quarter plane separately. For each tree (x,y): 1<=x<=20, 1<=y<=20, check if it's big enough, and not obscured by another tree, whose center is closer to the origin. It gives accurate enough results, at least for this judge's tests.

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am
Why are you dividing problem into quarter planes? How do you deal with trees on the border between planes?
You're never too old to become younger...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Why are you dividing problem into quarter planes?
That makes it easier for me to check for overlapping angular intervals -- I don't have to worry about signs of trig functions or circularity of angles.
How do you deal with trees on the border between planes?
There won't be such trees. Problem statement says that position of the observer will be such that d <= x,y <= 1-d, so a tree will at worst only touch the border between quarter planes. (of course, you should divide plane into quarters, relative to the observer, and not (0, 0) point.)

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am
Thanks, that makes sense.

EDIT: How do you check if tree is not obscured by another tree?
You're never too old to become younger...

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
if you see the conditions carefully you will understand that there will not be any tree on the border!

By the way, can any one tell me in case of: .1 .46 .38 (the given case) how many trees there will be in the 4 quadrents seperately?
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
oops... i did not see mf's reply!

anyway, you first sort the trees by distance. then you will save the angles in a vector/array. when you are going to add a range (angle) then you will see if it is intersected by any other angles. if so then you change the previous boundary if not you can see this tree.
Self judging is the best judging!