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

Post by Zhls » Tue Nov 09, 2004 3:28 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!!!
Beg your help!!!!!!

Zhls
New poster
Posts: 9
Joined: Sat Oct 16, 2004 2:14 pm

Post by Zhls » Wed Nov 10, 2004 11:34 am

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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Fri Dec 31, 2004 5:46 am

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:

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

Thanks in advance.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Fri Dec 31, 2004 8:30 am

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

Post by shanto86 » Tue May 30, 2006 7:04 am

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:

Post by mf » Tue May 30, 2006 7:06 am

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

Post by shanto86 » Tue May 30, 2006 9:16 am

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

Post by shanto86 » Fri Jun 02, 2006 2:42 am

some one please help!
Self judging is the best judging!

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am

Post by ar2rd » Sun Jun 04, 2006 2:40 am

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

Please Help.
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:

Post by mf » Tue Jun 20, 2006 8:56 pm

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

Post by ar2rd » Fri Jun 30, 2006 2:11 pm

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:

Post by mf » Fri Jun 30, 2006 3:15 pm

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

Post by ar2rd » Fri Jun 30, 2006 3:29 pm

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

Post by shanto86 » Fri Jun 30, 2006 4:06 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

Post by shanto86 » Fri Jun 30, 2006 4: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!

Post Reply

Return to “Volume 1 (100-199)”