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%
 
Total votes: 33

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 09, 2007 2:08 am

this problem looks exactly pick's theorem! :)
i cannot see any meaning of deriving pick's theorem from scratch! :D
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:

Post by mf » Mon Jul 09, 2007 2:38 am

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:

Post by andysoft » Sat Jul 14, 2007 12:49 pm

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;


    
    readln (xx1,yy1,xx2,yy2,xx3,yy3);

    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);
      readln (xx1,yy1,xx2,yy2,xx3,yy3);
    
    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:

Post by mf » Sat Jul 14, 2007 1:07 pm

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:

Post by andysoft » Sat Jul 14, 2007 4:06 pm

Thanks for your advice, mf.
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

Post by tgoulart » Sat Jul 14, 2007 7:06 pm

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:

Post by andysoft » Sun Jul 15, 2007 8:48 am

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

Post by Orlin » Sun Sep 30, 2007 8:09 pm

Hello Admins!

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 30, 2007 8:12 pm

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

Post by lantimilan » Sat Dec 01, 2007 5:04 pm

There are all too many TLE and WA complains about this problem.
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

Post by lantimilan » Sat Dec 01, 2007 5:05 pm

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

Post by kmkkmk » Sun Mar 08, 2009 5:44 pm

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;
}
Thank you for your consideration.

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

Re: 143 - need test cases

Post by phy » Tue Mar 10, 2009 7:52 am

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

Post by DD » Wed Jan 20, 2010 4:06 am

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;
}
Thank you for your consideration.
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. :D
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

Post by Taman » Fri Jan 14, 2011 11:59 pm

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?

Post Reply

Return to “Volume 1 (100-199)”