## 143 - Orchard Trees

Moderator: Board moderators

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

Yes
17
52%
No
16
48%

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
tan_Yui wrote:I couldn't find any bugs in my code, so I'll try to change the precision.
I changed the precision to 'long double' or 'float' from 'double', but my code couldn't output the value '1701'.
The reason for WA of my code might be in other place not in the precision.

My code has become complex...., so I'll rewrite whole of code.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am

### 143 - Orchard Trees

I know there are already a couple of posts regarding this, my program gives the correct output for the input I could find.

However I've gotten *tons* of WA's on this problem, I increased my precision to a very high degree and tested with all sorts of boundary cases, so I begin to wonder if the judge program is not precise enough for one of its cases?

I was just curious about what anyone who got AC on this problem had to do with their precision (did you increase it, or decrease it) or if there was something misleading in the problem statement (do we really only consider points from 1 to 99)?

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

### 143 Need help!

Code: Select all

``````/* ACM Problem Set */

/* Problem 143 */
/* Orchard Trees */

#include <cstdio>
#include <math.h>
#include <stdlib.h>
#define min(a,b) a < b ? a : b
#define max(a,b) a > b ? a : b
#define less0(a) a < 1 ? 1 : a
#define most100(a) a > 99 ? 99 : a
#define epsilon 0.00000001
using namespace std;

bool IsIntersectWithHorizont (int H, long double x1, long double y1, long double x2, long double y2)
{
if (y1 == y2) return false;
long double X = x2 - ((y2 - (long double)H) * (x2 - x1) / (y2 - y1));
if (((X >= x1) && (X <= x2)) || ((X <= x1) && (X >= x2))) return true;
else return false;
}

long double FindIntersectWithHorizont (int H, long double x1, long double y1, long double x2, long double y2)
{
return x2 - ((y2 - (long double)H) * (x2 - x1) / (y2 - y1));
}

int CountPointsOnLine (int H, long double x1, long double y1, long double x2, long double y2, long double x3, long double y3)
{
long double LeftPoint = 101, RightPoint = 0;
if (IsIntersectWithHorizont(H, x1, y1, x2, y2))
{
LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x1, y1, x2, y2));
RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x1, y1, x2, y2));
}
if (IsIntersectWithHorizont(H, x1, y1, x3, y3))
{
LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x1, y1, x3, y3));
RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x1, y1, x3, y3));
}
if (IsIntersectWithHorizont(H, x3, y3, x2, y2))
{
LeftPoint = min (LeftPoint, FindIntersectWithHorizont(H, x3, y3, x2, y2));
RightPoint = max (RightPoint, FindIntersectWithHorizont(H, x3, y3, x2, y2));
}
if (RightPoint > 99) RightPoint = 99.0;
if (RightPoint < 1) return 0;
if (LeftPoint < 1) LeftPoint = 1.0;
if (LeftPoint > 99) return 0;
return (int)(float(RightPoint + epsilon) - ceil(LeftPoint - epsilon) + 1);
}

int main()
{
long double x1, x2, x3, y1, y2, y3;
while (scanf("%llf %llf %llf %llf %llf %llf\n", &x1, &y1, &x2, &y2, &x3, &y3) == 6)
{
if (!(x1 || x2 || x3 || y1 || y2 || y3)) break;
int ans = 0;
if ((y1 == y2) && (y2 == y3))
{
if ((int)float(y1) == (int)ceil(y1)) ans = (most100(less0((int)float(max(x1,(max(x2,x3))) + epsilon))) - most100(less0((int)ceil(min(x1,(min(x2,x3))) - epsilon))));
if ((y1 == 100) || (y1 == 0)) ans = 0;
}
else
{
int B = most100(less0((int)ceil(min(y1,(min(y2,y3))) - epsilon)));
int T = most100(less0((int)float(max(y1,(max(y2,y3))) + epsilon)));
for (int y = B; y <= T; y++)
{
ans += CountPointsOnLine(y, x1, y1, x2, y2, x3, y3);
}
}
printf("%4d\n", ans);
}
}
``````

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

### 143 Ochard Trees WA......help,,,,

I'm getting WA .....
this makes me crazy...
My code do correctly in some test cases that are in this board...
but getting WA...
what is problem...
can anyone talk to me??
and is there a special cases??
help me.........

Code is deleted after I have accepted..
Last edited by yolongyi on Fri Feb 03, 2006 5:02 pm, edited 1 time in total.
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

### I accepted!!

I just change double to long double..
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

Joth
New poster
Posts: 11
Joined: Sat Mar 10, 2007 8:29 pm
can anyone with an AC on this problem tell me what they get with this data?

Code: Select all

``````1 1 50 1 100 1.01
1 1 100 1.01 1 1.01
0 0 0 0 0 0``````
thanks all!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns...

Code: Select all

``````  50
1``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Joth
New poster
Posts: 11
Joined: Sat Mar 10, 2007 8:29 pm
thanks Jan! i get the same...
could you give me your results for

Code: Select all

``````50 1 100 .99999 0 .99999
50 1 100 1.00001 0 1.00001
``````
does anyone know if there is a limit to the amount of precision on the input? I believe at one point in the problem the range is given as 0.0 to 100.0 and later as 0.00 to 100.00... does this mean input is limited to the hundredths position?
thanks again!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think the judge input is not that dirty. My code assumes that there is no number with more than 2 digits after the decimal point.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
I search only from min x to max x and from min y to max y, then calculate the area, but is still is TLE, look at my code:

Code: Select all

``````#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

long double xx1,yy1,xx2,yy2,xx3,yy3,eps=0.00001,s;

long double abs2(long double n) {
if (n<0)
return -n;
else
return n;
}

long double d(long double x1,long double y1,long double x2, long double y2) {
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

long double f(long double x1, long double y1, long double x2, long double y2, long double x3, long double y3) {
long double a = d(x1,y1,x2,y2), b = d(x1,y1,x3,y3), c = d(x2,y2,x3,y3),p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}

bool inside (int x, int y) {
long double
s1 = f(x,y,xx1,yy1,xx2,yy2),
s2 = f(x,y,xx2,yy2,xx3,yy3),
s3 = f(x,y,xx1,yy1,xx3,yy3);

return (abs2(s1+s2+s3-s) < eps);

}

long double min (long double a,long double b) {
return a<b?a:b;
}
long double max(long double a,long double b) {
return a>b?a:b;
}
long double min3 (long double a, long double b, long double c) {
return min(a,min(b,c));
}
long double max3 (long double a, long double b, long double c) {
return max(a,max(b,c));
}

int main(int argc, char *argv[]) {

long int x,y,ans;

cin >> xx1 >> yy1 >> xx2 >> yy2 >> xx3 >> yy3;

while (!((xx1==0)&&(xx2==0)&&(yy1==0)&&(yy2==0)&&(xx3==0)&&(yy3==0))) {

s = f(xx1,yy1,xx2,yy2,xx3,yy3);

ans = 0;
int xxx=int (floor(min3(xx1,xx2,xx3)));
if (xxx<1) xxx=1;
int xxxm=int (ceil(max3(xx1,xx2,xx3)));
if (xxxm>99) xxxm=99;
int yyy=int(floor(min3(yy1,yy2,yy3)));
if (yyy<1) yyy=1;
int yyym=int(ceil(max3(yy1,yy2,yy3)));
if (yyym>99) yyym=99;

for (x=xxx;x<=xxxm;x++)
for (y=yyy;y<=yyym;y++)
if (inside (x,y)) ans++;

printf ("%4d\n",ans);
cin >> xx1 >> yy1 >> xx2 >> yy2 >> xx3 >> yy3;

}

return EXIT_SUCCESS;
}

``````
Now I lay me down to sleep...
my profile

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

http://online-judge.uva.es/board/viewtopic.php?t=7805
Thiago Sonego Goulart - UFMG/Brazil

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Obviously a simple brute force method does not provide the response in the limited time. Try to improve your code a bit!

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
Actually, it is possible to get AC with a brute force method, but you must use a simpler way to see if the point is in the triangle. This one above is too slow.
Thiago Sonego Goulart - UFMG/Brazil

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
thanks a lot People, I will try to fix it as you said.
Now I lay me down to sleep...
my profile

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
A simple improvement which is applicable to your code is try not to use sqrt function. Also you can find out whether the point is inside or on the triangle or not. I know you can find its formula with a little knowledge of Euclidean geometry.

Spoiler: use the area for the determination.