143 - Orchard Trees

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

Should the judge tell us which test cases are messing us up?

Yes
17
52%
No
16
48%
 
Total votes: 33

zhiping85
New poster
Posts: 2
Joined: Tue Sep 13, 2011 10:57 am

143 Orchard Trees, no TLE, but WA

Post by zhiping85 » Sun Oct 09, 2011 4:56 pm

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
New poster
Posts: 1
Joined: Sun Oct 30, 2011 8:46 pm

[143] The least solved problem of volume 1. Here's why...

Post by epaik » Sun Oct 30, 2011 8:58 pm

:evil: 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
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

WA in 143

Post by happyson10 » Thu Dec 13, 2012 3:46 am

got AC now
Last edited by happyson10 on Fri Dec 14, 2012 2:07 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA in 143

Post by brianfry713 » Thu Dec 13, 2012 11:45 pm

Output should be right justified in a field of width 4.
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

Re: WA in 143

Post by happyson10 » Fri Dec 14, 2012 2:07 am

thanks.

Mates
New poster
Posts: 2
Joined: Thu Mar 14, 2013 10:11 am

143 Orchard Trees - WA

Post by Mates » Thu Mar 14, 2013 10:17 am

Removed after AC.
Last edited by Mates on Thu Mar 14, 2013 10:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 143 Orchard Trees - WA

Post by brianfry713 » Thu Mar 14, 2013 9:16 pm

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
Check input and AC output for thousands of problems on uDebug!

Mates
New poster
Posts: 2
Joined: Thu Mar 14, 2013 10:11 am

Re: 143 Orchard Trees - WA

Post by Mates » Thu Mar 14, 2013 10:43 pm

Thank you very much! Finally got AC :)

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 143 Orchard Trees - WA

Post by forthright48 » Sun Jan 19, 2014 10:39 am

Finally AC! :D 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
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

KYL
New poster
Posts: 2
Joined: Thu Jun 12, 2014 8:58 am

143 - Orchard Trees WA

Post by KYL » Thu Jun 12, 2014 9:04 am

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?
Last edited by KYL on Fri Jun 13, 2014 5:26 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 143 - Orchard Trees WA

Post by brianfry713 » Thu Jun 12, 2014 9:30 pm

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/
Check input and AC output for thousands of problems on uDebug!

KYL
New poster
Posts: 2
Joined: Thu Jun 12, 2014 8:58 am

Re: 143 - Orchard Trees WA

Post by KYL » Fri Jun 13, 2014 5:25 am

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

sady
New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

Re: 143 - Orchard Trees wa plz help

Post by sady » Sat Nov 01, 2014 8:28 pm

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
New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

Re: 143 - Orchard Trees

Post by sady » Sat Nov 01, 2014 8:29 pm

plz plz someone help.
what getting me wrong answer?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 143 - Orchard Trees

Post by lighted » Mon Nov 03, 2014 10:26 am

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 1 (100-199)”