Page **2** of **3**

Posted: **Tue Nov 09, 2004 3:28 pm**

by **Zhls**

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!!!
```

Beg your help!!!!!!

Posted: **Wed Nov 10, 2004 11:34 am**

by **Zhls**

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;
};
double radius;
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));
range = asin(radius/dist);
double center = atan2(p.y-observer.y, p.x-observer.x);
ar->from = center - range;
ar->to = center + range;
range *= 36000;
return ar;
}
void addToList(AngleRange* ar)
{
if (head==NULL)
{
head = 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 getQuadrant1Num(POINT observer)
{
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)
{
addToList(ar);
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;
radius = diameter/2.0;
tmp.x = x;
tmp.y = y;
num += getQuadrant1Num(tmp);
tmp.x = 1-y;
tmp.y = x;
num += getQuadrant1Num(tmp);
tmp.x = 1-x;
tmp.y = 1-y;
num += getQuadrant1Num(tmp);
tmp.x = y;
tmp.y = 1-x;
num += getQuadrant1Num(tmp);
cout<<num<<endl;
}
return 0;
}
```

SOS!

Help!

Help!

Help!!!

Posted: **Fri Dec 31, 2004 5:46 am**

by **stubbscroll**

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));
range = asin(radius/dist);
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:

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...

Thanks in advance.

Posted: **Fri Dec 31, 2004 8:30 am**

by **stubbscroll**

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.

### 149

Posted: **Tue May 30, 2006 7:04 am**

by **shanto86**

Can any one please help me to solve this problem?

Posted: **Tue May 30, 2006 7:06 am**

by **mf**

Are you getting WA or you just don't know how to solve it?

Posted: **Tue May 30, 2006 9:16 am**

by **shanto86**

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.

Posted: **Fri Jun 02, 2006 2:42 am**

by **shanto86**

some one please help!

Posted: **Sun Jun 04, 2006 2:40 am**

by **ar2rd**

I also have trouble with that problem. I don't know how to do it...

Please Help.

Posted: **Tue Jun 20, 2006 8:56 pm**

by **mf**

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.

Posted: **Fri Jun 30, 2006 2:11 pm**

by **ar2rd**

Why are you dividing problem into quarter planes? How do you deal with trees on the border between planes?

Posted: **Fri Jun 30, 2006 3:15 pm**

by **mf**

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.)

Posted: **Fri Jun 30, 2006 3:29 pm**

by **ar2rd**

Thanks, that makes sense.

EDIT: How do you check if tree is not obscured by another tree?

Posted: **Fri Jun 30, 2006 4:06 pm**

by **shanto86**

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?

Posted: **Fri Jun 30, 2006 4:10 pm**

by **shanto86**

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.