143 - Orchard Trees

[smilitude]

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!

[mf]

Pick's theorem only applies to polygons which have integer coordinates of the vertices, which isn't the case in this problem.

[andysoft]

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;
}

[mf]

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]

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...

[tgoulart]

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

[andysoft]

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.

[Orlin]

Hello Admins!

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

The 4th post in particular is interesting:

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]

I think the judge data is correct. Because I have changed all the input to 'int' and it worked well.

[lantimilan]

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.

[lantimilan]

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.

[kmkkmk]

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]

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]

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.

[Taman]

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?