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
149 - Forests
Moderator: Board moderators
-
ericschmidt
- New poster
- Posts: 16
- Joined: Mon Jan 06, 2003 9:27 pm
- Location: Grosskrut, Austria
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
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)
test?
-
Pedrinho UFPE
- New poster
- Posts: 15
- Joined: Tue Sep 10, 2002 1:56 am
- Location: Brasil
- Contact:
Forests
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..
I think I didn't understand the limit of the vision field of the guy.
0,01
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..
I think I didn't understand the limit of the vision field of the guy.
0,01
Interested
-
Pedrinho UFPE
- New poster
- Posts: 15
- Joined: Tue Sep 10, 2002 1:56 am
- Location: Brasil
- Contact:
Forests
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)
Interested
-
Pedrinho UFPE
- New poster
- Posts: 15
- Joined: Tue Sep 10, 2002 1:56 am
- Location: Brasil
- Contact:
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
149 - Forests
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]
- 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]
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
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.
- 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.
-
ericschmidt
- New poster
- Posts: 16
- Joined: Mon Jan 06, 2003 9:27 pm
- Location: Grosskrut, Austria
149 - Forests
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
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
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.
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?
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!
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!