Page 6 of 7

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

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

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

Posted: Sun Oct 30, 2011 8:58 pm
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
``````

### WA in 143

Posted: Thu Dec 13, 2012 3:46 am
got AC now

### Re: WA in 143

Posted: Thu Dec 13, 2012 11:45 pm
Output should be right justified in a field of width 4.

### Re: WA in 143

Posted: Fri Dec 14, 2012 2:07 am
thanks.

### 143 Orchard Trees - WA

Posted: Thu Mar 14, 2013 10:17 am
Removed after AC.

### Re: 143 Orchard Trees - WA

Posted: Thu Mar 14, 2013 9:16 pm
Use double instead of long double.
Use ceil and fabs from math.h

### Re: 143 Orchard Trees - WA

Posted: Thu Mar 14, 2013 10:43 pm
Thank you very much! Finally got AC

### Re: 143 Orchard Trees - WA

Posted: Sun Jan 19, 2014 10:39 am
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``

### 143 - Orchard Trees WA

Posted: 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?

### Re: 143 - Orchard Trees WA

Posted: 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/

### Re: 143 - Orchard Trees WA

Posted: Fri Jun 13, 2014 5:25 am
I modify the code for the eps and it get AC! Thank you!

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

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

### Re: 143 - Orchard Trees

Posted: Sat Nov 01, 2014 8:29 pm
plz plz someone help.

### Re: 143 - Orchard Trees

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