Page 1 of 3

149 - Forests

Posted: Thu Jun 06, 2002 9:59 pm
by opcode
Hi!

I need more test cases for this problem...
There is only *one* in the description and there is no way of knowing the correct answer to a test case you choose for yourself because there are no 'easy' test cases.
I am getting the correct result for that one given test case, but I get 'wrong answer' upon submission. One test case is just totally insufficient.
Please, those who have solved this problem, post some test cases.

greetings,
opcode

Posted: Fri Jun 07, 2002 3:11 pm
by wyvmak
i just randomly input two to my program:

input:
0.1 0.4 0.6
0.1 0.5 0.5

output:
134
132

Posted: Wed Jan 29, 2003 6:09 am
by ericschmidt
Hi opcode!

The on-line judge accepted my new C-code for "forests". My first algorithm was actually correct ... but the optimizing work on it (because of exceeded run-time limit) brought in an error which actually would have been easy to find if I would have used the obvious "extreme" input case:

0.5 0.5 0.5

which has to deliver the output:

4

which can simply be checked on a piece of paper.

Yours, Eric

Problem Forest (149)

Posted: Sun Feb 16, 2003 3:32 pm
by nghiank
test?

Forests

Posted: Sun Apr 13, 2003 2:32 am
by Pedrinho UFPE
Hi!

When I tried to solve this problem I found in my solution 312 trees in the firs quadrant (x > 0 && y > 0). It makes me crazy cause I didn't find any error in the logic or elsewhere.. :evil:

I think I didn't understand the limit of the vision field of the guy.
0,01

Posted: Mon Apr 14, 2003 1:37 am
by jpfarias
If you submit the number of the problem I'll read it...


JP

Forests

Posted: Mon Apr 14, 2003 3:12 am
by Pedrinho UFPE
I've already solved the problem. Anyway Thank you for the help. (The problem was 149, we can see it at acm.uva.es/p/v1/ the link Forests)

Posted: Mon Apr 14, 2003 3:24 am
by Pedrinho UFPE
Excuse me people! I've pressed the wrong button :(

149 - Forests

Posted: Thu Aug 14, 2003 10:46 pm
by Krzysztof Duleba
I have some doubts about this problem.

- does diameter really means diameter, or is it the radius? I've found sample test case on this board 0.5 0.5 0.5 with "right" answer 4, but it is right only when radius, not diameter, is equal 0.5.

- "Because the grid is infinite, the orgin is unimportant". But it is so only when the grid is infinite in every direction! Is it the case or should I focus on points (x,y) with x,y >=0 ?

- 0.01 degree means pi/18000, right?

Or maby it is something about my code? Can anyone take a look? It isn't fast (probably will get TLE), but now I want to get the right answers, optimalisations will come in future.


[cpp]#include <iostream>
#include <cmath>
#include <list>

using namespace std;


#define FLOAT_TYPE double
#define ZERO 0

#define quiet

const FLOAT_TYPE epsilon_angle=M_PI/18000, epsilon=sin(epsilon_angle/2),
M_3_PI_2=2*M_3PI_4;


typedef struct point
{
FLOAT_TYPE x, y;
};

point centre;
FLOAT_TYPE diameter, radius;

/* The distance between given points */
inline FLOAT_TYPE dist(point a, point b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}


/* The measure of angle abc */
inline FLOAT_TYPE angle(point a, point b, point c)
{
FLOAT_TYPE tmp=((a.x-b.x)*(c.x-b.x)+(a.y-b.y)*(c.y-b.y))/(dist(b,a)*dist(b,c));
if(tmp<=-1.0)return M_PI;
if(tmp>=1.0)return 0;
return acos(tmp);
}

/* Half of the measure of the angle subtended by pine with the centre its trunk in point a */
inline FLOAT_TYPE viewangle(point a)
{
FLOAT_TYPE tmp=radius/dist(a,centre);
if(tmp>=1.0)return M_PI_2;
if(tmp<=-1.0)return M_3_PI_2;
return asin(tmp);
}

/* does the point a blocks the point b? */
inline bool blockage(point a, point b)
{
if(abs(dist(a,centre)-dist(b,centre))<=ZERO)return false;
return (angle(a,centre,b)-viewangle(a)-viewangle(b)<=epsilon_angle);
}

bool cmp(const point & a, const point & b)
{
return (dist(a,centre)<dist(b,centre));
}


int main()
{
cin>>diameter;cin>>centre.x;cin>>centre.y;

while(diameter!=0||centre.x!=0||centre.y!=0)
{
radius=diameter/2;
FLOAT_TYPE max_dist=radius/epsilon;
int down=0, top=2+(int)max_dist;
list<point> q;
for(int i=down;i<=top;i++)for(int j=down;j<=top;j++)
{
point p;
p.x=i;p.y=j;
q.push_back(p);
}
q.sort(cmp);
/* now q stores points in ascending order in terms of distance from the centre. */

int result=0;
while(!q.empty())
{
result++;
point p=q.front();
if(dist(centre,p)>max_dist)break;
q.erase(q.begin());
list<point>::iterator i=q.begin();
#ifndef quiet
cout<<"Visible: "<<p.x<<' '<<p.y<<'\n';
cout<<"Blocked:\n";
#endif

/* remove all the points blocked by the point p */
while(i!=q.end())
if(blockage(p,*i))
{
list<point>::iterator tmp=i;
#ifndef quiet
cout<<" "<<tmp->x<<' '<<tmp->y<<'\n';
#endif
tmp++;
q.erase(i);
i=tmp;
}
else i++;
#ifndef quiet
cout<<'\n';
#endif
}
cout<<result<<endl;
cin>>diameter;cin>>centre.x;cin>>centre.y;
}
} [/cpp]

Posted: Sat Aug 23, 2003 11:43 pm
by Krzysztof Duleba
One of the Valladolid members gave me some hints and I got AC. Now I can ansewer my own questions :-)

- diameter really means diameter :-)
- the forest is infinite in every horizontal direction
- 0.01 degree is pi/18000
- the correct output for 0.5 0.5 0.5 is 4

The most important thing that I overlooked is the fact that partly visible trees make other trees invisible (or partly visible) too. I don't know why but I assumed that only completely visible trees can do this.

Posted: Wed Dec 10, 2003 7:04 pm
by junbin
Can anyone post more test data? My code gives the correct answers for all the given test data and all the test data I set myself (and manually verified)...

It would be great if someone can use his/her AC code to generate some test results for the rest of us.....

Posted: Wed Dec 10, 2003 7:05 pm
by junbin
Can you post more test data? My code gives the correct answers for all the test data ever posted that I can find and all the test data I set myself (and manually verified)...

It would be great if you can use your AC code to generate some test results for the rest of us.....

149 - Forests

Posted: Sat Dec 13, 2003 3:07 pm
by ericschmidt
Dear junbin,

Here are some more test cases from my AC program. Note that each test case can potentially be used with 8 input variations which can be achieved with the following operations:

x <--> (1-x)
y <--> (1-y)
x <--> y

These 8 variations should always deliver the same results. You can check the "symmetry handling" of your program that way. ;-)

here the new test cases:
0.43 0.5 0.5
0.25 0.25 0.33
0.15 0.18 0.46
0.15 0.16 0.19
0.125 0.46 0.5

here the results:
12
24
58
61
80

Yours, Eric

Posted: Sat Dec 13, 2003 5:30 pm
by junbin
I went over my code again and surprise surprise... I found the error. :) Seems like my calculation of the angle subtended at the eye is wrong.. I forgot to asin it :p... since the values are generally very small and sin( x) -> x when x is small, so I managed to get correct answers for most cases... anyway , my code has been accepted now. Thank you very much! :)



---- BELOW IS THE ORIGINAL POST BEFORE EDIT ----
Thank you very much for your input!

I ran my the numbers through my program and the only differences are:

0.15 0.18 0.46
59 <- my output

0.15 0.16 0.19
62 <- my output


Seeing as how the answers differ by just a little bit, my guess is that it's a rounding off/floating point error... and I can't seem to isolate it yet.. so I'll work harder. :p


I've generated the list of coordinates added by my programs into the counting.. if you have time, would you mind if you check if they are right?


Quadrant 1 means the top right hand corner.
Quadrant 2 means the top left hand corner.
Quadrant 3 means the bottom left hand corner.
Quadrant 4 means the bottom right hand corner.

What my program does is that after it computes the trees in quadrant 1, it rotates the entire map 90 degrees so that quadrant 2 is now quadrant 1 (y, 1-x), so I just run the code over the data again with the viewpoint rotated. Quadrant 3= quadrant 2 rotated 90 degrees and quadrant 4 = quadrant 3 rotated 90 degrees.

Therefore, in quadrant 3, ADD: 1, 1 actually means the point (-1, -1) and so on.


Code: Select all

0.15 0.18 0.46
Quadrant: 1
ADD: 1 1
ADD: 1 2
ADD: 1 3
ADD: 1 4
ADD: 1 5
ADD: 1 6
ADD: 2 7
ADD: 2 5
ADD: 2 2
ADD: 2 3
ADD: 3 5
ADD: 3 4
ADD: 2 1
ADD: 3 1
ADD: 4 1
ADD: 4 2
Quadrant: 2
ADD: 1 1
ADD: 1 2
ADD: 1 3
ADD: 1 4
ADD: 2 5
ADD: 2 2
ADD: 2 3
ADD: 3 5
ADD: 3 4
ADD: 4 3
ADD: 6 4
ADD: 2 1
ADD: 7 2
Quadrant: 3
ADD: 1 1
ADD: 1 2
ADD: 2 1
ADD: 3 1
ADD: 4 1
ADD: 6 2
ADD: 2 2
ADD: 3 2
ADD: 5 3
ADD: 4 3
ADD: 5 4
ADD: 3 4
ADD: 4 5
Quadrant: 4
ADD: 1 1
ADD: 1 2
ADD: 1 3
ADD: 2 4
ADD: 3 6
ADD: 2 1
ADD: 3 1
ADD: 4 1
ADD: 5 1
ADD: 6 1
ADD: 7 2
ADD: 5 2
ADD: 8 3
ADD: 2 2
ADD: 3 2
ADD: 4 3
ADD: 4 5
59


0.15 0.16 0.19
Quadrant: 1
ADD: 1 1
ADD: 1 2
ADD: 1 3
ADD: 1 4
ADD: 1 5
ADD: 1 6
ADD: 2 5
ADD: 2 3
ADD: 3 5
ADD: 3 4
ADD: 4 5
ADD: 2 1
ADD: 3 1
ADD: 4 1
ADD: 5 1
ADD: 5 2
ADD: 3 2
ADD: 5 3
ADD: 4 3
ADD: 5 4
Quadrant: 2
ADD: 1 1
ADD: 1 2
ADD: 1 3
ADD: 1 4
ADD: 1 5
ADD: 1 6
ADD: 2 7
ADD: 2 4
ADD: 2 5
ADD: 2 2
ADD: 2 3
ADD: 3 3
ADD: 4 4
ADD: 6 5
ADD: 3 2
ADD: 4 3
Quadrant: 3
ADD: 1 1
ADD: 1 2
ADD: 2 4
ADD: 2 5
ADD: 2 6
ADD: 2 1
ADD: 3 2
ADD: 4 2
ADD: 5 2
ADD: 6 3
ADD: 6 4
Quadrant: 4
ADD: 1 1
ADD: 2 1
ADD: 3 1
ADD: 4 1
ADD: 5 1
ADD: 6 1
ADD: 4 2
ADD: 2 2
ADD: 3 2
ADD: 3 3
ADD: 4 4
ADD: 5 6
ADD: 2 3
ADD: 3 4
ADD: 3 6
62

Can anyone give me some hints on the Pro.149?

Posted: Tue Nov 09, 2004 3:31 am
by Zhls
I am very sad to face the problem 149.
For I have no good way to get it!
And also I am afraid the double precision(can I get the right answer?).
Can someone give me some hints?
I'm waiting for your warm heart!