149 - Forests

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

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

[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:

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]

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]

Can any one please help me to solve this problem?

[mf]

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

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

[shanto86]

some one please help!

[ar2rd]

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

Please Help.

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

[ar2rd]

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

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

[ar2rd]

Thanks, that makes sense.

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

[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?

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