143 - Orchard Trees

[zhiping85]

Tried all test cases on this thread and passed them all. But somehow still getting WA. Below is my code:

Code: Select all

Removed after A/C

Any form of assistance is greatly appreciated .

EDIT: The problem states that the coordinates are given in the range of 0.00 to 100.00, therefore one could simply multiply by 100 to get integer coordinates, and do all computations using integers!

[epaik]

After finally solving this problem, I really wish somebody told me the "trick" in this question.

When the problem defines that:

Each line will contain 6 real numbers in the range 0.00 to 100.00

what it's really implying is that the precision of all calculations should be done to 2 decimal places. If this were explicitly defined in the problem I certainly wouldn't have spent more than an hour solving this... Anyways, an easy way to go about this is to multiply the inputs (which are constrained to two decimal places) by 100, resulting in only integer math used throughout the problem.

The rest of the problem is a simple application of geometry (dot or cross products, your choice).

Here's a little bit of sample input and output, note the linear case:

Code: Select all

0 0 1 1 2 2
1 1 1 1 1.1 1.1
71.67 88.3 45.02 49.09 98.49 0.1
1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
0 0 0 0 0 0

Here's my output:

Code: Select all

   2
   1
1701
  15
  17

[happyson10]

got AC now

[brianfry713]

Output should be right justified in a field of width 4.

[happyson10]

thanks.

[Mates]

Removed after AC.

[brianfry713]

Your I/O is correct. Your problem is probably a precision error. I made your code AC by these changes:
Use double instead of long double.
Use ceil and fabs from math.h

[Mates]

Thank you very much! Finally got AC

[forthright48]

Finally AC! Didn't consider that triangles can be collinear

Input:

Code: Select all

1 1 2 2 3 3
0 0 0 0 0 0

Output:

Code: Select all

3

[KYL]

This is the code

Code: Select all

Removed after AC

This is input

Code: Select all

1.5 1.5 1.5 6.8 6.8 1.5
10.7 6.9 8.5 1.5 14.5 1.5
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6
1.2 1.1 1.1 2.2 2.2 5.5
10.3 6.2 6.63 2.36 3.21 3.32
0.0 0.0 100.0 100.0 100.0 0.0
0.0 0.0 3.0 3.0 3.0 0.0
71.67 88.3 45.02 49.09 98.49 0.1
0 0 100 0 0 100
0.1 0.1 0.9 100 0.7 80
1 1 5 5 100 100
0 0 2.5 0.5 4 0.7
1 1 3 2 2 3
1 1 5 1 5 5
0.99999 0.99999 1.00001 0.99999 0.99999 1.00001
0 0 0 0 100 0
50.00 0.00 50.00 50.00 50.00 100.00
50.00 50.00 50.00 50.00 50.00 50.00
1 1 1 1 1 1
1 1 1 1 1.1 1.1
1 1 1 5 1 10
1 1 1 4 2 4
1 1 1 4 4 1
1 1 1 2 1 1
0 0 0 2 2 0
98 98 100 98 98 100
0 0 0 5 0.5 0
3.01 3.01 3.01 3.99 3.99 3.01
1 2 3 5 6 9
1 1 2 2 3 3
5 4 3.2 3.6 1.0 0.6 1.2
1.1 1.1 2.2 2.2 5.5 10.3
6.2 6.63 2.36 3.21 3.32
0.5 0.5 1.5 1.5 0.5 1.5
0 50 50 50 100 50
1 50 5 50 10 50
0 0 50 50 100 100
0 0 50 50 100 99
100 100 100 100 100 100
0 0 0 50 0 100
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
0 0 50 50 100 0
0 0  0 0  0 0

This is output

Code: Select all

  15
  17
   3
   3
   2
   0
  10
4950
   6
1701
4950
   0
  99
   0
   4
  15
   1
   0
  99
   1
   1
   1
  10
   5
  10
   2
   1
   4
   0
   0
   3
   3
   2
   0
  10
   1
  99
  10
  99
  50
   0
   0
   0
2500

Can anyone check the output / code?

[brianfry713]

Your I/O is correct. I'm guessing it's a precision error. I used 1e-9 for EPS in my AC code.
http://floating-point-gui.de/

[KYL]

I modify the code for the eps and it get AC! Thank you!

[sady]

Code: Select all

#include<cstdio>
#include<math.h>
#include<algorithm>
#define eps 1e-9
using namespace std;
class p
{
    public:
    double x,y;
    p(){}
    p(double x, double y)
    {
        this->x=x;
        this->y=y;
    }
};
p a[3];
double Area;

void lowest_y()
{
    int i=0;
    for(int k=1;k<3;++k)
    {
        if(a[k].y<a[i].y || (a[k].y==a[i].y && a[k].x>a[i].x)  )
            i=k;
    }
    p t;
    t=a[0];
    a[0]=a[i];
    a[i]=t;
    return;
}
int compare(double a, double b)
{
    if( a-b <eps && b-a < eps) return 0;//means equal
    else if( a-b<eps )return -1;
    return 1;
}
double area( p z, p x, p y )
{
    return (0.5*( ( x.x-z.x)*(y.y-z.y)-(x.y-z.y)*(y.x-z.x)) );
}
double dis( p x, p y )
{
    return sqrt ( (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y) );
}
bool  ccw(p z, p x, p y)
{
    double a= ((x.x-z.x)*(y.y-z.y) -(x.y-z.y)*(y.x-z.x));
    if( compare(a,0.0)==1 ) return true;
    return false;
    /*if (a>0)return true;
    return false;*/

}

bool  cw(p z, p x, p y)
{
    return  ( ( x.x-z.x)*(y.y-z.y)-(x.y-z.y)*(y.x-z.x) ) <0;
}
bool colinear(p z, p x, p y)
{
    //printf("%lf %lf %lf\n", dis(x,y) , dis(z,x) , dis(z,y) );
    return  fabs( dis(x,y)-dis(z,x)-dis(z,y) ) < 1e-9;
}
bool inside_triangle(p z)
{
    //double aa=0.0, temp;
    for(int m=0;m<3;++m)
    {
         //temp=area( z, a[m], a[(m+1)%3] );
         //aa+=temp;
       if(!ccw( z, a[m], a[(m+1)%3] ) )
       return false;

    }
    /*if( fabs(aa-Area)<1e-9)*/return true;
    /*return false;*/

}
bool onborder( p z)
{
    for(int m=0;m<3;++m)
    {
        if(colinear( z, a[m], a[(m+1)%3] ) )
        {
             //printf("on %d %d ", m,m+1);
             return true;
        }

    }
    return false;
}
int main()
{
    //freopen("out.txt", "w", stdout);
    int c=0,j,point;
    p t;
    int minx, maxx, miny, maxy, i;
    double mix, miy, mx,my;
    while(1)
    {
        for( j=0;j<3;++j)
        {
            scanf("%lf %lf", &a[j].x, &a[j].y);
            if(!a[j].x && !a[j].y)++c;
        }
        if(c==3)break;
        c=0;
        //lowest_y();
        if( !ccw(a[0],a[1], a[2]) )
        {
            t=a[1];
            a[1]=a[2];
            a[2]=t;
        }
        Area = fabs(area(a[0],a[1],a[2]));
        minx = mix = min(ceil(a[0].x), min( ceil(a[1].x), ceil(a[2].x ) ) );
        minx = max(1, minx);
        miny = miy = min(ceil(a[0].y), min(  ceil(a[1].y), ceil(a[2].y) ) );
        miny = max(1, miny);

        maxx= mx = max( floor(a[0].x), max(floor(a[1].x), floor(a[2].x) ) );
        maxx= min(99, maxx);
        maxy= my = max(floor(a[0].y), max(floor(a[1].y), floor(a[2].y)  ) );
        maxy= min(99, maxy);
        point=0;
        for(i=minx; i<= maxx ; ++i)
        {
            for(j=miny; j<=maxy ; ++j)
            {
                if(onborder(p(i,j))  ||  inside_triangle(p(i,j))  )
                {
                    ++point;

                }

            }
        }
        printf("%4d\n",point );

    }
    return 0;
}

[sady]

plz plz someone help.
what getting me wrong answer?

[lighted]

Input

Code: Select all

73.00 98.22 8.50 95.66 66.27 13.55
64.27 41.32 80.08 78.29 22.12 28.56
28.63 91.29 99.35 12.04 48.30 74.61
19.23 91.24 60.25 46.96 77.53 12.41
0 0 0 0 0 0

Correct Output

Code: Select all

2720
 677
 189
 327