![:)](./images/smilies/icon_smile.gif)
i cannot see any meaning of deriving pick's theorem from scratch!
![:D](./images/smilies/icon_biggrin.gif)
i will suggest to do a google and get AC! thats the sweetie thing!
Moderator: Board moderators
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.
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;
}
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
Is it possible that the judges' solution is not accurate enough and therefore the correct answer is actually wrong?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!!
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
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;
}
Code: Select all
35.0 31.9 3.5 63.4 66.5 46.6
Maybe you can try to add EPS to ceil() and floor(). For example, you can call ceil(x - EPS) and floor(x + EPS).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
and that is the source although I doubt it is helpfulCode: 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
Thank you for your consideration.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; }
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?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