Page 6 of 7
143 Orchard Trees, no TLE, but WA
Posted: Sun Oct 09, 2011 4:56 pm
by zhiping85
Tried all test cases on this thread and passed them all. But somehow still getting WA. Below is my code:
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
by 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:
WA in 143
Posted: Thu Dec 13, 2012 3:46 am
by happyson10
got AC now
Re: WA in 143
Posted: Thu Dec 13, 2012 11:45 pm
by brianfry713
Output should be right justified in a field of width 4.
Re: WA in 143
Posted: Fri Dec 14, 2012 2:07 am
by happyson10
thanks.
143 Orchard Trees - WA
Posted: Thu Mar 14, 2013 10:17 am
by Mates
Removed after AC.
Re: 143 Orchard Trees - WA
Posted: Thu Mar 14, 2013 9:16 pm
by 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
Re: 143 Orchard Trees - WA
Posted: Thu Mar 14, 2013 10:43 pm
by Mates
Thank you very much! Finally got AC
Re: 143 Orchard Trees - WA
Posted: Sun Jan 19, 2014 10:39 am
by forthright48
Finally AC!
Didn't consider that triangles can be collinear
Input:
Output:
143 - Orchard Trees WA
Posted: Thu Jun 12, 2014 9:04 am
by KYL
This is the code
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
by 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/
Re: 143 - Orchard Trees WA
Posted: Fri Jun 13, 2014 5:25 am
by KYL
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
by 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;
}
Re: 143 - Orchard Trees
Posted: Sat Nov 01, 2014 8:29 pm
by sady
plz plz someone help.
what getting me wrong answer?
Re: 143 - Orchard Trees
Posted: Mon Nov 03, 2014 10:26 am
by 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