OJ Board

Posted: **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!

i will suggest to do a google and get AC! thats the sweetie thing!

Posted: **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.

Posted: **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;
}

Posted: **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.

Posted: **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...

Posted: **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

Posted: **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.

Posted: **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?

Posted: **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.

Posted: **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.

Posted: **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.

Posted: **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

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.

Posted: **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

Posted: **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

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.

Posted: **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?

OJ Board

143 - Orchard Trees

143 Precision Issues

TLE and WA

Another speed up

143 - need test cases

Re: 143 - need test cases

Re: 143 - need test cases

Re: 143 Orchard Tree TLE