## 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%

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

### 143 Orchard Trees, no TLE, but WA

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

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

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

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

thanks.

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

### 143 Orchard Trees - WA

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

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

Thank you very much! Finally got AC

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

### Re: 143 Orchard Trees - WA

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

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

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

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

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

### Re: 143 - Orchard Trees wa plz help

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;
}
``````

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

### Re: 143 - Orchard Trees

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

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