## 143 - Orchard Trees

Moderator: Board moderators

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

Yes
17
52%
No
16
48%

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
this problem looks exactly pick's theorem!
i cannot see any meaning of deriving pick's theorem from scratch!
i will suggest to do a google and get AC! thats the sweetie thing!
fahim
#include <smile.h>

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Pick's theorem only applies to polygons which have integer coordinates of the vertices, which isn't the case in this problem.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Now I made my inside-checking function faster, but I now get some error (WA) because of precision (i think) and something connected to it.

my codes:

Code: Select all

``````program project2;
{\$APPTYPE CONSOLE}
{\$R-}{\$S-}{\$Q-}

var
xx1,yy1,xx2,yy2,xx3,yy3,eps,s: extended;
x,y,ans: longint;
xxx,xxxm,yyy,yyym: longint;

function d(x1,y1,x2,y2: extended): extended;
begin
result := sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
end;

function f(x1,y1,x2,y2,x3,y3: extended): extended;
begin
result := abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
end;

function inside (x,y: extended): boolean;
var
s1,s2,s3: extended;
begin

s1 := f(x,y,xx1,yy1,xx2,yy2);
s2 := f(x,y,xx2,yy2,xx3,yy3);
s3 := f(x,y,xx1,yy1,xx3,yy3);

result := (abs(s1+s2+s3-s) <= eps);
end;

function min (a,b: extended): extended;
begin
result := a;
if b<a then result := b
end;
function max (a,b: extended): extended;
begin
result := a;
if b>a then result := b
end;
function min3(a,b,c: extended): extended;
begin
result := min(a,min(b,c));
end;
function max3(a,b,c: extended): extended;
begin
result := max(a,max(b,c));
end;

begin
eps := 0.0000001;

while (not((xx1=0)and(xx2=0)and(yy1=0)and(yy2=0)and(xx3=0)and(yy3=0))) do
begin
s := f(xx1,yy1,xx2,yy2,xx3,yy3);

ans := 0;

xxx := round(min3(xx1,xx2,xx3));
if (xxx<1) then xxx:=1;

xxxm :=round(max3(xx1,xx2,xx3));
if (xxxm>99) then xxxm:=99;

yyy := round(min3(yy1,yy2,yy3));
if (yyy<1) then yyy:=1;

yyym:=round(max3(yy1,yy2,yy3));
if (yyym>99) then yyym:=99;

for x:=xxx to xxxm do
for y := yyy to yyym do
if (inside (x,y)) then ans:=ans+1;

writeln (ans:4);

end;

end.
``````
same in cpp

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.000001,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));*/
return abs2((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
}

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
When a polygon is defined by its vertices' coordinates, it's much more numerically stable to compute its area via vector cross products than by Heron's formula: area of triangle ABC is |AB x AC|/2.
In two dimensions cross product of vectors (x1, y1) and (x2, y2) is just x1 y2 - x2 y1.

In fact, you can use just the cross products to check whether a point is inside a polygon.
If ABC is oriented counter-clockwise, then point P is inside ABC iff PA x PB > 0, PB x PC > 0 and PC x PA > 0. (the cross products here are defined by the expression above.)

Edit:
I hadn't noticed at first that Heron's was commented out in your code.

Try to use a smaller epsilon, like 1e-9. And maybe do rounding with epsilons, too -- floor(x+eps), ceil(x-eps), etc.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
But I did both things you told me and it didn't help. Again WA at nearly the same time (~7.1 secs).
Don't even know what to do...
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
Try these:

Code: Select all

``````1 1 1 1 1.1 1.1
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
0 0  0 0  0 0``````

Code: Select all

``````   1
0``````
Thiago Sonego Goulart - UFMG/Brazil

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Thank you for the test cases, tgoulart!
I understood my mistake:
In 1st testcase (1 1 1 1 1.1 1.1) my program would ceil 1.1 to 2 and will find more points in answer than needed. I left it as it was, but in the loop (for x=... for y=...) I have added condition: if these x and y are not more than xmax, ymax and not less than ymin, xmin. And now, after 2,5 weeks I got AC.
Now I lay me down to sleep...
my profile

Orlin
New poster
Posts: 2
Joined: Sun Sep 30, 2007 7:54 pm

### 143 Precision Issues

I stumbled over this thread: http://online-judge.uva.es/board/viewtopic.php?t=637

The 4th post in particular is interesting:
click xx wrote:oh,I got AC now.But it's just unbelievable!!!
I changed the the const value esp in my program from 1e-10 to 1e-9 and
it got AC.I think there something wrong with the judge!!It cost me so my time on this stupid problem!!
Is it possible that the judges' solution is not accurate enough and therefore the correct answer is actually wrong?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think the judge data is correct. Because I have changed all the input to 'int' and it worked well.
Ami ekhono shopno dekhi...
HomePage

lantimilan
New poster
Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU
Contact:

### TLE and WA

For TLE, two improvements might be:
1. use a good polygon area computation routine, search mathworld.com for an idea
2. check points from minx to maxx only
I got several TLE because I forgot to cache triangle area values but did three computation in the same function. After using a temp var to cache trig area value I got AC in 2.45s.

For WA, the widely known test case should give output 1701, as far as my AC program goes.
-- This is Unix, any explanatory error message is seen as a sign of weakness

lantimilan
New poster
Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU
Contact:

### Another speed up

For C++ users, someone told me that cin/cout are in general much slower, maybe 10x, than scanf/printf, so consider this if you still got TLE.
-- This is Unix, any explanatory error message is seen as a sign of weakness

kmkkmk
New poster
Posts: 1
Joined: Sun Mar 08, 2009 5:34 pm

### 143 - need test cases

Hi

I cant find the problem with my program (it results in WA). Below is a list of input/outpot of my program:

Code: Select all

``````92.3 75.3 30.9 97.4 14.4 91.0
62.4 1.1 15.9 62.0 4.0 79.5
1.2 27.8 69.9 27.7 26.7 67.8
71.3 53.6 54.8 93.5 16.3 55.3
9.1 78.5 39.8 90.1 6.0 11.6
80.2 4.3 25.8 55.9 96.6 99.2
18.3 30.2 10.7 20.5 86.2 87.5
88.1 55.0 95.7 86.3 76.9 43.0
27.2 81.9 48.7 83.1 67.3 31.5
97.0 7.5 34.6 48.7 57.9 19.8
35.1 33.4 19.6 14.4 79.6 7.4
5.0 58.2 4.6 79.2 69.2 63.7
44.0 84.1 90.5 44.8 59.8 51.2
14.9 10.9 75.5 42.6 49.5 39.5
52.9 36.8 60.5 7.2 39.1 95.0
23.8 61.6 13.4 72.0 29.6 83.3
61.9 87.3 99.4 38.8 19.2 71.9
31.7 13.1 84.5 3.4 9.8 27.4
70.8 39.0 69.3 0.1 31.5 15.7
40.6 64.8 54.3 66.9 21.1 3.2
78.7 90.7 40.4 31.5 11.7 91.5
49.6 16.5 93.2 96.3 1.4 47.1
19.6 42.4 78.2 94.9 91.0 35.4
57.5 67.0 64.1 59.7 81.5 23.9
27.5 93.9 49.1 24.5 71.1 79.4
66.4 19.7 34.1 90.1 62.7 67.7
36.5 44.6 19.0 55.8 84.4 55.3
74.3 70.4 73.0 52.6 74.0 42.6
45.4 96.3 58.0 18.2 64.6 98.1
83.2 22.1 43.9 83.0 54.3 86.4
53.3 47.0 29.9 48.6 44.9 74.9
92.4 73.6 14.9 14.4 34.4 30.4
62.2 99.5 99.8 11.2 24.0 18.8
0.3 25.3 52.8 76.8 14.6 6.3
71.2 50.2 38.8 42.5 36.3 94.6
9.2 76.0 23.7 7.3 26.9 50.1
79.1 2.9 8.7 72.9 16.5 38.4
17.1 28.7 94.7 70.7 6.2 26.0
88.0 53.4 79.6 35.3 96.6 82.3
26.1 79.2 64.6 0.1 86.2 70.8
96.9 5.1 17.6 66.9 76.9 58.3
35.0 31.9 3.5 63.4 66.5 46.6
5.8 56.8 88.5 28.2 89.2 2.2
43.9 82.6 73.5 93.0 79.8 90.5
14.8 8.5 59.4 59.6 69.4 78.0
52.8 33.1 44.4 24.4 59.1 34.3
22.7 59.0 97.4 21.0 49.5 22.8
61.7 85.8 82.3 87.8 39.1 10.3
31.6 11.7 68.3 52.6 29.8 66.7
69.7 36.5 53.4 17.1 19.4 54.2
39.5 62.4 38.2 83.9 41.1 42.5
78.6 88.2 24.2 80.7 31.7 30.0
48.4 14.9 77.1 45.3 21.3 86.3
86.5 39.7 62.1 11.1 11.8 74.9
57.4 65.6 47.1 76.7 1.4 62.2
95.4 91.4 33.0 73.5 91.0 18.7
65.5 17.3 18.0 39.3 81.7 6.2
36.3 42.1 3.0 4.8 71.3 94.5
74.4 68.0 88.9 69.6 93.9 82.1
44.3 94.6 42.9 35.4 84.6 38.4
83.3 20.5 27.9 32.0 74.2 26.9
53.2 45.3 12.8 97.8 64.7 14.2
91.2 71.2 98.8 63.4 54.3 70.7
61.1 97.0 83.8 28.2 44.9 58.2
0.2 22.9 68.7 93.0 34.6 46.6
70.0 48.7 21.7 91.5 24.2 34.1
8.1 74.4 7.7 56.3 46.8 90.4
79.9 0.2 92.6 21.1 36.5 78.9
17.0 25.1 77.6 87.7 26.1 66.2
87.9 51.9 63.6 52.5 16.6 22.8
26.9 77.8 48.5 49.1 6.2 10.3
96.8 3.6 1.5 15.9 96.8 98.6
34.8 28.5 86.5 80.6 86.5 86.1
4.7 54.1 72.4 45.2 76.1 42.4
43.8 80.0 57.4 43.0 98.7 30.0
13.6 6.8 42.4 8.6 88.4 18.3
51.7 31.7 28.3 73.4 79.8 74.8
22.5 57.5 81.3 39.2 69.5 62.1
60.6 83.4 66.3 4.8 59.1 50.6
30.7 9.2 51.2 1.6 49.7 6.2
69.5 34.9 37.2 66.3 39.4 94.5
39.6 60.7 22.1 32.9 29.0 82.0
77.4 86.6 7.1 97.7 51.6 70.3
48.5 11.4 93.1 62.3 41.3 26.8
86.4 37.3 46.0 60.1 31.7 14.1
56.4 63.1 31.0 25.9 21.3 2.7
94.3 89.0 16.0 90.5 11.0 58.2
65.3 14.8 2.9 56.3 1.6 46.5
3.2 40.5 87.9 53.0 91.3 34.0
73.3 66.3 72.9 18.6 81.9 22.3
12.1 92.2 26.8 84.4 3.5 78.9
82.2 17.0 11.8 49.0 93.0 66.2
20.0 43.9 96.8 14.8 83.6 54.7
91.1 69.7 81.7 12.6 74.2 10.0
61.0 95.6 67.7 77.2 64.9 98.5
99.0 20.2 52.7 42.0 54.5 86.1
70.9 46.1 5.6 8.7 44.2 74.4
8.0 72.9 90.6 73.3 34.8 30.9
78.8 98.8 76.6 70.1 56.4 18.2
16.9 23.6 61.5 36.7 46.9 6.7
``````

Code: Select all

``````380
45
1393
1070
1008
3004
111
130
567
422
625
681
455
317
17
141
1324
271
744
402
2002
2590
2079
56
1358
644
360
24
764
383
318
42
3207
865
852
418
920
126
43
2214
1493
741
1064
69
156
26
841
756
1044
633
4
1406
1437
1496
330
2230
84
214
87
1230
126
328
146
996
394
1334
350
954
962
378
1029
4501
150
78
676
100
1089
564
150
41
487
330
716
527
1092
116
1276
334
823
207
131
1908
1342
202
46
1040
1427
1752
231
572
``````
and that is the source although I doubt it is helpful

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

inline bool isEqual(long double x, long double y)
{
const double epsilon = 1e-9 /* some small number such as 1e-5 */;
return std::abs(x - y) <= epsilon * std::abs(x);
// see Knuth section 4.2.2 pages 217-218
}

int main()
{
bool debug = false;

long double Ax, Ay, Bx, By, Cx, Cy;
while(std::cin >> Ax >> Ay >> Bx >> By >> Cx >> Cy)
{
//assert(Ax >= 0 && Ay >= 0 && Bx >= 0 && By >= 0 && Cx >= 0 && Cy >= 0);

if (Ax == 0 && Ay == 0 && Bx == 0 && By == 0 && Cx == 0 && Cy == 0)
break;

/* all points share the same y coordinate */
using std::swap;
if (isEqual(Ay, By) && isEqual(By, Cy)) {
if (Ax > Bx) { swap(Ax, Bx); swap(Ay, By); } // post: A < B
if (Bx > Cx) { swap(Bx, Cx); swap(By, Cy); } // post: B < C
if (Ax > Bx) { swap(Ax, Bx); swap(Ay, By); } // post: A < B

if (debug) /* points in order */
std::cout << "  " << Ax << " " << Ay << " " << Bx << " " <<
By << " " << Cx << " " << Cy << "\n";

if (debug)
std::cout << "  floor(Cx): " << std::floor(Cx) << "\n" <<
"  ceil(Ax): " << std::ceil(Ax) << "\n";

std::cout << 1 + std::floor(Cx) - std::ceil(Ax) << "\n";
continue;
}

//assert(!(isEqual(Ax, By) && isEqual(By, Cy)));

/* floodfill triangle from bottom to top and left to right.
*
* rename Points:
* - C at top, A at bottom  (Ay <= By <= Cy)
* - if A and B are at same height, ensure B is left of A (Bx <= Ax)
*/

/* Ay <= By <= Cy */
if (Ay > By) { swap(Ax, Bx); swap(Ay, By); } // post: A < B
if (By > Cy) { swap(Bx, Cx); swap(By, Cy); } // post: B < C
if (Ay > By) { swap(Ax, Bx); swap(Ay, By); } // post: A < B

// Bx <= Ax
if (isEqual(Ay, By) && Ax < Bx) { swap(Ax, Bx); swap(Ay, By); }

if (debug) /* points in order */
std::cout << "  " << Ax << " " << Ay << " " << Bx << " " << By <<
" " << Cx << " " << Cy << "\n";

unsigned N = 0;

using std::floor; using std::ceil;

if (debug)
std::cout << "  ceil(Ay)=" << ceil(Ay) << ", floor(By)=" <<
floor(By) << "\n";

for (int y = ceil(Ay); y <= floor(By); ++y) {

long double xLeft;
long double xRight;

if (isEqual(Ay, By)) {
xLeft = Bx;
} else {
xLeft = Ax + (y - Ay)*(Ax - Bx)/(Ay - By);
}

if (isEqual(Cy, Ay)) { // impossible, this implies Ay==By==Cy.
//assert(false);
//xRight = Ax;
} else {
xRight = Cx + (y - Cy)*(Cx - Ax)/(Cy - Ay);
}

if (xLeft > xRight)
swap(xLeft, xRight);

for (int x = ceil(xLeft); x <= floor(xRight); ++x) {
if (debug)
std::cout << "  Testing (" << x << ", " << y << ")\n";

++N;
}
}

if (debug)
std::cout << "  1+floor(By)=" << 1+floor(By) << ", floor(Cy)=" <<
floor(Cy) << "\n";

for (int y = 1 + floor(By); y <= floor(Cy); ++y) {

long double xLeft;
long double xRight;

if (isEqual(Cy, By)) { // impossible y = By is already processed
//assert(false);
//xLeft = Bx;
} else {
xLeft = Cx + (y - Cy)*(Cx - Bx)/(Cy - By);
}

if (isEqual(Cy, Ay)) { // impossible, this implies Ay==By==Cy.
//assert(false);
//xRight = Ax;
} else {
xRight = Cx + (y - Cy)*(Cx - Ax)/(Cy - Ay);
}

if (xLeft > xRight)
swap(xLeft, xRight);

for (int x = ceil(xLeft); x <= floor(xRight); ++x) {
if (debug)
std::cout << "  adding (" << x << ", " << y << ")\n";

++N;
}
}

std::cout << N << "\n";
}

return 0;
}
``````

phy
New poster
Posts: 3
Joined: Sat Apr 26, 2008 8:41 am

### Re: 143 - need test cases

It seems you didn't right justified the output in a field of width 4.

Btw, for this test case, the solution should be 743, not 741:

Code: Select all

``35.0 31.9 3.5 63.4 66.5 46.6``
You may find this tool useful:
http://uvatoolkit.com/problemssolve.php

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 143 - need test cases

kmkkmk wrote:Hi

I cant find the problem with my program (it results in WA). Below is a list of input/outpot of my program:

Code: Select all

``````92.3 75.3 30.9 97.4 14.4 91.0
62.4 1.1 15.9 62.0 4.0 79.5
1.2 27.8 69.9 27.7 26.7 67.8
71.3 53.6 54.8 93.5 16.3 55.3
9.1 78.5 39.8 90.1 6.0 11.6
80.2 4.3 25.8 55.9 96.6 99.2
18.3 30.2 10.7 20.5 86.2 87.5
88.1 55.0 95.7 86.3 76.9 43.0
27.2 81.9 48.7 83.1 67.3 31.5
97.0 7.5 34.6 48.7 57.9 19.8
35.1 33.4 19.6 14.4 79.6 7.4
5.0 58.2 4.6 79.2 69.2 63.7
44.0 84.1 90.5 44.8 59.8 51.2
14.9 10.9 75.5 42.6 49.5 39.5
52.9 36.8 60.5 7.2 39.1 95.0
23.8 61.6 13.4 72.0 29.6 83.3
61.9 87.3 99.4 38.8 19.2 71.9
31.7 13.1 84.5 3.4 9.8 27.4
70.8 39.0 69.3 0.1 31.5 15.7
40.6 64.8 54.3 66.9 21.1 3.2
78.7 90.7 40.4 31.5 11.7 91.5
49.6 16.5 93.2 96.3 1.4 47.1
19.6 42.4 78.2 94.9 91.0 35.4
57.5 67.0 64.1 59.7 81.5 23.9
27.5 93.9 49.1 24.5 71.1 79.4
66.4 19.7 34.1 90.1 62.7 67.7
36.5 44.6 19.0 55.8 84.4 55.3
74.3 70.4 73.0 52.6 74.0 42.6
45.4 96.3 58.0 18.2 64.6 98.1
83.2 22.1 43.9 83.0 54.3 86.4
53.3 47.0 29.9 48.6 44.9 74.9
92.4 73.6 14.9 14.4 34.4 30.4
62.2 99.5 99.8 11.2 24.0 18.8
0.3 25.3 52.8 76.8 14.6 6.3
71.2 50.2 38.8 42.5 36.3 94.6
9.2 76.0 23.7 7.3 26.9 50.1
79.1 2.9 8.7 72.9 16.5 38.4
17.1 28.7 94.7 70.7 6.2 26.0
88.0 53.4 79.6 35.3 96.6 82.3
26.1 79.2 64.6 0.1 86.2 70.8
96.9 5.1 17.6 66.9 76.9 58.3
35.0 31.9 3.5 63.4 66.5 46.6
5.8 56.8 88.5 28.2 89.2 2.2
43.9 82.6 73.5 93.0 79.8 90.5
14.8 8.5 59.4 59.6 69.4 78.0
52.8 33.1 44.4 24.4 59.1 34.3
22.7 59.0 97.4 21.0 49.5 22.8
61.7 85.8 82.3 87.8 39.1 10.3
31.6 11.7 68.3 52.6 29.8 66.7
69.7 36.5 53.4 17.1 19.4 54.2
39.5 62.4 38.2 83.9 41.1 42.5
78.6 88.2 24.2 80.7 31.7 30.0
48.4 14.9 77.1 45.3 21.3 86.3
86.5 39.7 62.1 11.1 11.8 74.9
57.4 65.6 47.1 76.7 1.4 62.2
95.4 91.4 33.0 73.5 91.0 18.7
65.5 17.3 18.0 39.3 81.7 6.2
36.3 42.1 3.0 4.8 71.3 94.5
74.4 68.0 88.9 69.6 93.9 82.1
44.3 94.6 42.9 35.4 84.6 38.4
83.3 20.5 27.9 32.0 74.2 26.9
53.2 45.3 12.8 97.8 64.7 14.2
91.2 71.2 98.8 63.4 54.3 70.7
61.1 97.0 83.8 28.2 44.9 58.2
0.2 22.9 68.7 93.0 34.6 46.6
70.0 48.7 21.7 91.5 24.2 34.1
8.1 74.4 7.7 56.3 46.8 90.4
79.9 0.2 92.6 21.1 36.5 78.9
17.0 25.1 77.6 87.7 26.1 66.2
87.9 51.9 63.6 52.5 16.6 22.8
26.9 77.8 48.5 49.1 6.2 10.3
96.8 3.6 1.5 15.9 96.8 98.6
34.8 28.5 86.5 80.6 86.5 86.1
4.7 54.1 72.4 45.2 76.1 42.4
43.8 80.0 57.4 43.0 98.7 30.0
13.6 6.8 42.4 8.6 88.4 18.3
51.7 31.7 28.3 73.4 79.8 74.8
22.5 57.5 81.3 39.2 69.5 62.1
60.6 83.4 66.3 4.8 59.1 50.6
30.7 9.2 51.2 1.6 49.7 6.2
69.5 34.9 37.2 66.3 39.4 94.5
39.6 60.7 22.1 32.9 29.0 82.0
77.4 86.6 7.1 97.7 51.6 70.3
48.5 11.4 93.1 62.3 41.3 26.8
86.4 37.3 46.0 60.1 31.7 14.1
56.4 63.1 31.0 25.9 21.3 2.7
94.3 89.0 16.0 90.5 11.0 58.2
65.3 14.8 2.9 56.3 1.6 46.5
3.2 40.5 87.9 53.0 91.3 34.0
73.3 66.3 72.9 18.6 81.9 22.3
12.1 92.2 26.8 84.4 3.5 78.9
82.2 17.0 11.8 49.0 93.0 66.2
20.0 43.9 96.8 14.8 83.6 54.7
91.1 69.7 81.7 12.6 74.2 10.0
61.0 95.6 67.7 77.2 64.9 98.5
99.0 20.2 52.7 42.0 54.5 86.1
70.9 46.1 5.6 8.7 44.2 74.4
8.0 72.9 90.6 73.3 34.8 30.9
78.8 98.8 76.6 70.1 56.4 18.2
16.9 23.6 61.5 36.7 46.9 6.7
``````

Code: Select all

``````380
45
1393
1070
1008
3004
111
130
567
422
625
681
455
317
17
141
1324
271
744
402
2002
2590
2079
56
1358
644
360
24
764
383
318
42
3207
865
852
418
920
126
43
2214
1493
741
1064
69
156
26
841
756
1044
633
4
1406
1437
1496
330
2230
84
214
87
1230
126
328
146
996
394
1334
350
954
962
378
1029
4501
150
78
676
100
1089
564
150
41
487
330
716
527
1092
116
1276
334
823
207
131
1908
1342
202
46
1040
1427
1752
231
572
``````
and that is the source although I doubt it is helpful

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

inline bool isEqual(long double x, long double y)
{
const double epsilon = 1e-9 /* some small number such as 1e-5 */;
return std::abs(x - y) <= epsilon * std::abs(x);
// see Knuth section 4.2.2 pages 217-218
}

int main()
{
bool debug = false;

long double Ax, Ay, Bx, By, Cx, Cy;
while(std::cin >> Ax >> Ay >> Bx >> By >> Cx >> Cy)
{
//assert(Ax >= 0 && Ay >= 0 && Bx >= 0 && By >= 0 && Cx >= 0 && Cy >= 0);

if (Ax == 0 && Ay == 0 && Bx == 0 && By == 0 && Cx == 0 && Cy == 0)
break;

/* all points share the same y coordinate */
using std::swap;
if (isEqual(Ay, By) && isEqual(By, Cy)) {
if (Ax > Bx) { swap(Ax, Bx); swap(Ay, By); } // post: A < B
if (Bx > Cx) { swap(Bx, Cx); swap(By, Cy); } // post: B < C
if (Ax > Bx) { swap(Ax, Bx); swap(Ay, By); } // post: A < B

if (debug) /* points in order */
std::cout << "  " << Ax << " " << Ay << " " << Bx << " " <<
By << " " << Cx << " " << Cy << "\n";

if (debug)
std::cout << "  floor(Cx): " << std::floor(Cx) << "\n" <<
"  ceil(Ax): " << std::ceil(Ax) << "\n";

std::cout << 1 + std::floor(Cx) - std::ceil(Ax) << "\n";
continue;
}

//assert(!(isEqual(Ax, By) && isEqual(By, Cy)));

/* floodfill triangle from bottom to top and left to right.
*
* rename Points:
* - C at top, A at bottom  (Ay <= By <= Cy)
* - if A and B are at same height, ensure B is left of A (Bx <= Ax)
*/

/* Ay <= By <= Cy */
if (Ay > By) { swap(Ax, Bx); swap(Ay, By); } // post: A < B
if (By > Cy) { swap(Bx, Cx); swap(By, Cy); } // post: B < C
if (Ay > By) { swap(Ax, Bx); swap(Ay, By); } // post: A < B

// Bx <= Ax
if (isEqual(Ay, By) && Ax < Bx) { swap(Ax, Bx); swap(Ay, By); }

if (debug) /* points in order */
std::cout << "  " << Ax << " " << Ay << " " << Bx << " " << By <<
" " << Cx << " " << Cy << "\n";

unsigned N = 0;

using std::floor; using std::ceil;

if (debug)
std::cout << "  ceil(Ay)=" << ceil(Ay) << ", floor(By)=" <<
floor(By) << "\n";

for (int y = ceil(Ay); y <= floor(By); ++y) {

long double xLeft;
long double xRight;

if (isEqual(Ay, By)) {
xLeft = Bx;
} else {
xLeft = Ax + (y - Ay)*(Ax - Bx)/(Ay - By);
}

if (isEqual(Cy, Ay)) { // impossible, this implies Ay==By==Cy.
//assert(false);
//xRight = Ax;
} else {
xRight = Cx + (y - Cy)*(Cx - Ax)/(Cy - Ay);
}

if (xLeft > xRight)
swap(xLeft, xRight);

for (int x = ceil(xLeft); x <= floor(xRight); ++x) {
if (debug)
std::cout << "  Testing (" << x << ", " << y << ")\n";

++N;
}
}

if (debug)
std::cout << "  1+floor(By)=" << 1+floor(By) << ", floor(Cy)=" <<
floor(Cy) << "\n";

for (int y = 1 + floor(By); y <= floor(Cy); ++y) {

long double xLeft;
long double xRight;

if (isEqual(Cy, By)) { // impossible y = By is already processed
//assert(false);
//xLeft = Bx;
} else {
xLeft = Cx + (y - Cy)*(Cx - Bx)/(Cy - By);
}

if (isEqual(Cy, Ay)) { // impossible, this implies Ay==By==Cy.
//assert(false);
//xRight = Ax;
} else {
xRight = Cx + (y - Cy)*(Cx - Ax)/(Cy - Ay);
}

if (xLeft > xRight)
swap(xLeft, xRight);

for (int x = ceil(xLeft); x <= floor(xRight); ++x) {
if (debug)
std::cout << "  adding (" << x << ", " << y << ")\n";

++N;
}
}

std::cout << N << "\n";
}

return 0;
}
``````
Maybe you can try to add EPS to ceil() and floor(). For example, you can call ceil(x - EPS) and floor(x + EPS).

I followed this rule and got A.C. in one shot.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 143 Orchard Tree TLE

tgoulart wrote:Try these:

Code: Select all

``````1 1 1 1 1.1 1.1
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
0 0 0 0 0 0``````

Code: Select all

`````` 1
0``````
well i can't understand how 1 1 1 1 1.1 1.1 points make a triangle. I also found a similar test case by Sohel bro which says that 1 1 2 2 3 3 as a valid input. Am i missing something?