143 - Orchard Trees

[10153EN]

Sometimes the precision of the judge's data is not as good as ours.

So we can solve it by declaring the variables as float instead of double.

However I donno if it apply to this problem =p

[rgrig]

It happened to me also... My solution was also wrong because of a to good precision
Here it is:

#include <stdio.h>
#include <math.h>


const double EPSILON = 1e-9; // *** WA with 1e-15 ***


double x1, y1;
double x2, y2;
double x3, y3;


// helpers


inline double minimum(double& a, double& b, double& c)
{
double min = a;
if (b < min) min = b;
if (c < min) min = c;
return ceil(min - EPSILON);
}


inline double maximum(double& a, double& b, double& c)
{
double max = a;
if (b > max) max = b;
if (c > max) max = c;
return ceil(max + EPSILON);
}




inline int equal(double& x, double y)
{
return fabs(x - y) < EPSILON;
}


inline int NotSplit(double& dx1, double& dy1,
double& dx2, double& dy2,
double& dx3, double& dy3)
{
// compute vector products
double vect_prod_12 = dy2 * dx1 - dy1 * dx2;
double vect_prod_13 = dy3 * dx1 - dy1 * dx3;

// may be it is on the edge ...
if (equal(vect_prod_12, 0.))
return 0;
if (equal(vect_prod_13, 0.))
return 0;

// .. or not
return (vect_prod_12 < 0.) == (vect_prod_13 < 0.);
}




inline int IsInside(double& xp, double& yp)
{
double dx1 = x1 - xp; // vector pointing from tree to (x1, y1)
double dy1 = y1 - yp;
double dx2 = x2 - xp; // vector pointing from tree to (x2, y2)
double dy2 = y2 - yp;
double dx3 = x3 - xp; // vector pointing from tree to (x3, y3)
double dy3 = y3 - yp;

if (NotSplit(dx1, dy1, dx2, dy2, dx3, dy3))
return 0;
if (NotSplit(dx2, dy2, dx3, dy3, dx1, dy1))
return 0;
if (NotSplit(dx3, dy3, dx1, dy1, dx2, dy2))
return 0;

return 1;
}



// Read and write

inline int ReadCoord()
{
fscanf(stdin, "%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
return !((x1==0) && (x2==0) && (x3==0) && (y1==0) && (y2==0) && (y3==0));
}



// Assume x1, x2... are in the interval [0;100]
void CountAndWrite()
{
unsigned cntNodes = 0;
double i, j;

double xmin = minimum(x1, x2, x3);
double ymin = minimum(y1, y2, y3);
double xmax = maximum(x1, x2, x3);
double ymax = maximum(y1, y2, y3);

if (xmax > 100.) xmax = 100.;
if (ymax > 100.) ymax = 100.;
if (xmin < 1.) xmin = 1.;
if (ymin < 1.) ymin = 1.;

for (i = xmin; i < xmax; ++i)
{
for (j = ymin; j < ymax; ++j)
{
if (IsInside(i, j))
++cntNodes;
}
}
fprintf(stdout, "%4d\n", cntNodes);
}



int main()
{
while (ReadCoord())
{
CountAndWrite();
}

return 0;
}

[obayashi]

yes, the problem mainly lies in the precision...

[htl]

Why does this code get WA? I think my algo isn't wrong. Maybe it's the problem of range of points(1~99?) or precision...
[c]
#include<stdio.h>
#define CHECK(lx1,ly1,lx2,ly2,px,py) ((lx2-lx1)*(py-ly1)-(px-lx1)*(ly2-ly1))
void main(void)
{
int x,a,b,c,d,y,ans;
double p[3][2],left,right,up,down;
while(1)
{
scanf("%lf %lf %lf %lf %lf %lf",&p[0][0],&p[0][1],&p[1][0],&p[1][1],&p[2][0],&p[2][1]);
if(p[0][0]==0 && p[0][1]==0 && p[1][0]==0 && p[1][1]==0 && p[2][0]==0 && p[2][1]==0)
break;
for(x=0,left=101;x<3;x++)
if(p[x][0]<left)
left=p[x][0];
for(x=0,right=-1;x<3;x++)
if(p[x][0]>right)
right=p[x][0];
for(x=0,up=-1;x<3;x++)
if(p[x][1]>up)
up=p[x][1];
for(x=0,down=101;x<3;x++)
if(p[x][1]<down)
down=p[x][1];
for(a=1;a<left;a++)
;
if(a!=1)
a--;
for(b=99;b>right;b--)
;
if(b!=99)
b++;
for(c=1;c<down;c++)
;
if(c!=1)
c--;
for(d=99;d>up;d--)
;
if(d!=99)
d++;
ans=0;
for(x=a;x<=b;x++)
for(y=c;y<=d;y++)
if((CHECK(p[0][0],p[0][1],p[1][0],p[1][1],x,y)>=0 && CHECK(p[1][0],p[1][1],p[2][0],p[2][1],x,y)>=0 && CHECK(p[2][0],p[2][1],p[0][0],p[0][1],x,y)>=0) || (CHECK(p[0][0],p[0][1],p[1][0],p[1][1],x,y)<=0 &&
CHECK(p[1][0],p[1][1],p[2][0],p[2][1],x,y)<=0 && CHECK(p[2][0],p[2][1],p[0][0],p[0][1],x,y)<=0))
ans++;
printf("%d\n",ans);
}
}
[/c]

[LTH]

I have passed the problem by Brute Force Check all the points.
Nowadays,i tried to solve the problem by "Scanline Method"
But it turns out to be wrong answer.....><
So,is there any special test cases for the problem???
Or,is there any thing to notice about solveing the problem by scanline method?

[Yarin]

I also had these problems when going from "brute force" to scanline. You just have to be extra careful with those epsilon values when doing the limit checking! Try generate a large bunch of inputs and compare your scanline solution with the brute force solution, that's what I did. Hopefully you'll find a mismatch then and can check more closely for the error.

[LTH]

i have tried what u say.....but it seems that it doesnt work..

those are some inputs and outputs my program return:
0 0 100 0 0 100
4950
0.1 0.1 0.9 100 0.7 80
0
1 1 5 5 100 100
99
0 0 2.5 0.5 4 0.7
0
1 1 3 2 2 3
4
1 1 5 1 5 5
15
0.99999 0.99999 1.00001 0.99999 0.99999 1.00001
1

this is my code:
[cpp]
#include <stdio.h>
#include <math.h>

class point
{
public:
double x,y;
};

double max(double a,double b)
{
if(a>b)
return a;
return b;
}

double min(double a,double b)
{
if(a<b)
return a;
return b;
}

bool range(double x,double a,double b)
{
if(x>=min(a,b)&&x<=max(a,b))
return 1;
return 0;
}

void main()
{
bool usable[3];
long i,j,k,sum,tmp;
double y1,y2,y3,s1,s2,s3,m1,m2,m3,M1,M2,M3,start,end,t;
point p[3],s,e,rs,re;
while(scanf("%lf %lf %lf %lf%lf %lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y)!=EOF)
{
if(p[0].x==0&&p[0].y==0&&p[1].x==0&&p[1].y==0&&p[2].x==0&&p[2].y==0)
break;
s.x=100,s.y=100,e.x=0,e.y=0;
for(i=0;i<3;i++)
{
if(p.x<s.x)
s.x=p.x;
if(p.y<s.y)
s.y=p.y;
if(p.x>e.x)
e.x=p.x;
if(p.y>e.y)
e.y=p.y;
}
rs=s;
re=e;
m1=min(p[0].x,p[1].x),M1=max(p[0].x,p[1].x);
m2=min(p[1].x,p[2].x),M2=max(p[1].x,p[2].x);
m3=min(p[2].x,p[0].x),M3=max(p[2].x,p[0].x);
start=ceil(s.x),end=floor(e.x);
if(start==0)
start=1;
if(end==100)
end=99;
for(sum=0,t=start;t<=end;t++)
{
for(j=0;j<3;j++)
usable[j]=1;
if(p[0].x!=p[1].x&&(double)t>=m1&&(double)t<=M1)
y1=(p[0].y*(p[1].x-t)+p[1].y*(t-p[0].x))/(p[1].x-p[0].x);
else
usable[0]=0,y1=999999;
if(p[1].x!=p[2].x&&(double)t>=m2&&(double)t<=M2)
y2=(p[1].y*(p[2].x-t)+p[2].y*(t-p[1].x))/(p[2].x-p[1].x);
else
usable[1]=0,y2=999999;
if(p[2].x!=p[0].x&&(double)t>=m3&&(double)t<=M3)
y3=(p[2].y*(p[0].x-t)+p[0].y*(t-p[2].x))/(p[0].x-p[2].x);
else
usable[2]=0,y3=999999;
if((usable[0]||usable[1]||usable[2])==0)
{
s1=floor(re.y)-ceil(rs.y)+1;
if(range(0,rs.y,re.y))
s1--;
if(range(100,rs.y,re.y))
s1--;
sum+=s1;
}
else
{
s1=floor(max(y1,y2))-ceil(min(y1,y2))+1;
s2=floor(max(y2,y3))-ceil(min(y2,y3))+1;
s3=floor(max(y3,y1))-ceil(min(y3,y1))+1;
if(range(0,y1,y2))
s1--;
if(range(100,y1,y2))
s1--;
if(range(0,y2,y3))
s2--;
if(range(100,y2,y3))
s2--;
if(range(0,y3,y1))
s3--;
if(range(100,y3,y1))
s3--;
if(usable[2]==0)
sum+=s1;
else if(usable[0]==0)
sum+=s2;
else if(usable[1]==0)
sum+=s3;
else
sum+=min(min(max(s1,s2),max(s2,s3)),max(s3,s1));

}
}
printf("%4ld\n",sum);
}
}
[/cpp]

[LTH]

ok...finally...coincidently...i figure out what happened to my code...
its the problem of preciseness...
double is not precise enough.....
i simple change all double to long double and then passed.....
its really a little shit...i think.....

[40093ZR]

I solved this problem in C++ with VisualStudio2003 under WinXP.
It works perfectly but online-judje gave me CE.
Then I wrote it in JAVA with Sun1Studio and it works perfectly
but again I received CE.
I have by now 24 CE in my rank! After 24 modifications.
Why?

[shamim]

Most probably you are using fucntions supported by your compiler and not by Standard C++.

Post your code to see the real reason.

[Tahseen Mohammad]

you may post your code. That will make easy to comment.

You may try compiling it in LINUX or Cygwin g++ in windows.

And check whether you send your code as C when it should be
C++.

Also enable e-mail reply and check the compiler error given
in the reply.

[Heartattack!]

I'm quite a novice at problem solving. (I'm more into game programming ) I recently entered this weird world and have started losing hair . I presume from the forrum that the problem with this problem is the precission. I know zilch about precission . Can someone tell me why I get a WA. Here's my code. The logic is plain geometry...
Oh, and something about precission would be just fabulous, babe

[cpp]
#include "stdio.h"
#include "io.h"//"io.h" for open() close() in VC++.NET2K3
#include "fcntl.h"

inline int IsIn(float x1, float y1, float x2, float y2, float x3, float y3, float x, float y);
inline void Init(void);

float fCo[3][2];
float fMaxx,fMinx,fMaxy,fMiny,fiInit,fjInit,fiTerm,fjTerm;


int main(void)
{
#ifndef ONLINE_JUDGE //I remove this part before submitting. I
// also remove io.h && fcntl.h
close(0);open("in.txt",O_RDONLY);
close(1);open("out.txt",O_WRONLY|O_CREAT,0600);
#endif
for(int p=0;p<3;p++)//I like to init everything
{
fCo[p][0]=0;
fCo[p][1]=0;
}

fMaxx=0;
fMaxy=0;
fMinx=0;
fMiny=0;

scanf("%f%f%f%f%f%f",&fCo[0][0],&fCo[0][1],
&fCo[1] [0],&fCo[1][1],&fCo[2][0],&fCo[2][1]);

while(fCo[0][0]||fCo[0][1]||
fCo[1][0]||fCo[1][1]||
fCo[2][0]||fCo[2][1])
{
Init();

int iCount=0;
for(float i=fiInit;i<fiTerm;i++)
for(float j=fjInit;j<fjTerm;j++)
{
if(IsIn(fCo[0][0],fCo[0][1],fCo[1][0],
fCo[1][1],fCo[2][0],fCo[2][1],i,j))
if(IsIn(fCo[1][0],fCo[1][1],fCo[2][0],
fCo[2][1],fCo[0][0],fCo[0][1],i,j))
if(IsIn(fCo[2][0],fCo[2][1],fCo[0][0],
fCo[0][1],fCo[1][0],fCo[1][1],i,j))
iCount++;
}

printf("%4d\n",iCount);

scanf("%f%f%f%f%f%f",&fCo[0][0],&fCo[0][1],
&fCo[1][0],&fCo[1][1],&fCo[2][0],&fCo[2][1]);



}




return 0;
}

//Main() Done.
///////////////////////
///////////////////////
//IsIn()
inline int IsIn(float x1, float y1, float x2, float y2, float x3, float y3, float x, float y)
{

float l=((y1-y2)*(x3-x1))-((x1-x2)*(y3-y1));//Geometry...
float m=((y1-y2)*(x-x1))-((x1-x2)*(y-y1));//Same here...

//Next bit is to see if all four points are on the same line...
//My prog ran less than one second when I didn't consider this!
if(l==0)
{
if(m==0)//(i,j) on that line
{
if((x>=fMinx)&&(x<=fMaxx)&&
(y>=fMiny)&&(y<=fMaxy))
return 1;
else return 0;
}
else return 0;
}

//Next to check if 3 points are not on the same line and
//that (i,j) is on the same side as the 3rd point of the line
//joining first 2 points or if (i,j) is on that line.

if((l>0&&m>0)||(l<0&&m<0)||(m==0))//m==0... if error goes
//through once or even twice
//It'll get caught
// the third time
return 1;
else
return 0;
}//IsIn() Done
/////////////
////////////
//Init()
inline void Init(void)
{
fMaxx=fCo[0][0];
fMinx=fCo[0][0];
fMaxy=fCo[0][1];
fMiny=fCo[0][1];

for(int i=0;i<3;i++)//Find Min and Max x and y
{
if(fCo[0]>=fMaxx)
fMaxx=fCo[0];
if(fCo[0]<=fMinx)
fMinx=fCo[0];

if(fCo[1]>=fMaxy)
fMaxy=fCo[1];
if(fCo[1]<=fMiny)
fMiny=fCo[1];
}


//I'm doing this bit to reduce the number of cycles.
//I ran into Time Over when I didn't.

if(fMinx==0)
fiInit=1;//No trees on x and y axes
else
fiInit=(float)((int)fMinx);//Doublecast(!) to avoid
//the pesky warning...
if(fMiny==0)
fjInit=1;
else
fjInit=(float)((int)fMiny);

if(fMaxx==100)//No trees on x=100 and y=100
fiTerm=100;
else
fiTerm=(float)((int)(fMaxx+1));
if(fMaxy==100)
fjTerm=100;
else
fjTerm=(float)((int)(fMaxy+1));

}[/cpp][/cpp]

[Heartattack!]

I'm quite a novice at problem solving. (I'm more into game programming ) I recently entered this weird world and have started losing hair . I presume from the forrum that the problem with this problem is the precission. I know zilch about precission . Can someone tell me why I get a WA. Here's my code. The logic is plain geometry...
Oh, and something about precission would be just fabulous, babe

[cpp]

#include "stdio.h"
#include "io.h"//"io.h" for open() close() in VC++.NET2K3
#include "fcntl.h"

inline int IsIn(float x1, float y1, float x2, float y2, float x3, float y3, float x, float y);
inline void Init(void);

float fCo[3][2];
float fMaxx,fMinx,fMaxy,fMiny,fiInit,fjInit,fiTerm,fjTerm;


int main(void)
{
#ifndef ONLINE_JUDGE //I remove this part before submitting. I
// also remove io.h && fcntl.h
close(0);open("in.txt",O_RDONLY);
close(1);open("out.txt",O_WRONLY|O_CREAT,0600);
#endif
for(int p=0;p<3;p++)//I like to init everything
{
fCo[p][0]=0;
fCo[p][1]=0;
}

fMaxx=0;
fMaxy=0;
fMinx=0;
fMiny=0;

scanf("%f%f%f%f%f%f",&fCo[0][0],&fCo[0][1],
&fCo[1] [0],&fCo[1][1],&fCo[2][0],&fCo[2][1]);

while(fCo[0][0]||fCo[0][1]||
fCo[1][0]||fCo[1][1]||
fCo[2][0]||fCo[2][1])
{
Init();

int iCount=0;
for(float i=fiInit;i<fiTerm;i++)
for(float j=fjInit;j<fjTerm;j++)
{
if(IsIn(fCo[0][0],fCo[0][1],fCo[1][0],
fCo[1][1],fCo[2][0],fCo[2][1],i,j))
if(IsIn(fCo[1][0],fCo[1][1],fCo[2][0],
fCo[2][1],fCo[0][0],fCo[0][1],i,j))
if(IsIn(fCo[2][0],fCo[2][1],fCo[0][0],
fCo[0][1],fCo[1][0],fCo[1][1],i,j))
iCount++;
}

printf("%4d\n",iCount);

scanf("%f%f%f%f%f%f",&fCo[0][0],&fCo[0][1],
&fCo[1][0],&fCo[1][1],&fCo[2][0],&fCo[2][1]);



}




return 0;
}

//Main() Done.
///////////////////////
///////////////////////
//IsIn()
inline int IsIn(float x1, float y1, float x2, float y2, float x3, float y3, float x, float y)
{

float l=((y1-y2)*(x3-x1))-((x1-x2)*(y3-y1));//Geometry...
float m=((y1-y2)*(x-x1))-((x1-x2)*(y-y1));//Same here...

//Next bit is to see if all four points are on the same line...
//My prog ran less than one second when I didn't consider this!
if(l==0)
{
if(m==0)//(i,j) on that line
{
if((x>=fMinx)&&(x<=fMaxx)&&
(y>=fMiny)&&(y<=fMaxy))
return 1;
else return 0;
}
else return 0;
}

//Next to check if 3 points are not on the same line and
//that (i,j) is on the same side as the 3rd point of the line
//joining first 2 points or if (i,j) is on that line.

if((l>0&&m>0)||(l<0&&m<0)||(m==0))//m==0... if error goes
//through once or even twice
//It'll get caught
// the third time
return 1;
else
return 0;
}//IsIn() Done
/////////////
////////////
//Init()
inline void Init(void)
{
fMaxx=fCo[0][0];
fMinx=fCo[0][0];
fMaxy=fCo[0][1];
fMiny=fCo[0][1];

for(int i=0;i<3;i++)//Find Min and Max x and y
{
if(fCo[0]>=fMaxx)
fMaxx=fCo[0];
if(fCo[0]<=fMinx)
fMinx=fCo[0];

if(fCo[1]>=fMaxy)
fMaxy=fCo[1];
if(fCo[1]<=fMiny)
fMiny=fCo[1];
}


//I'm doing this bit to reduce the number of cycles.
//I ran into Time Over when I didn't.

if(fMinx==0)
fiInit=1;//No trees on x and y axes
else
fiInit=(float)((int)fMinx);//Doublecast(!) to avoid
//the pesky warning...
if(fMiny==0)
fjInit=1;
else
fjInit=(float)((int)fMiny);

if(fMaxx==100)//No trees on x=100 and y=100
fiTerm=100;
else
fiTerm=(float)((int)(fMaxx+1));
if(fMaxy==100)
fjTerm=100;
else
fjTerm=(float)((int)(fMaxy+1));

}[/cpp]

[sohel]

I don't know why I got TLE in this problem..

Is my method of point_in_triangle too costly or is my breaking condition wrong.

for point_in_triangle :
I calculate the area of the given tringle.
then I run the loop
[c]
for(i=1;i<100;i++)
for(j=1;j<100;j++)
if( in_the_triangle(i,j) )
inside++;
[/c]

for input taking :
I use .. scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
if( x1==0 && y1==0 && x2==0 && y2==0 && x3==0 && y3==0)
break;

in_the_triangle(int i, int j)
{
pichhi_area = sum of three triangles having one vertex as (i,j) and any of the two vertex of the main triangle.

if( pichhi_area == main_area ) inside;
otherwise outside.
}

Some hints would be appreciated.

[Whinii F.]

As far as I am concerned, there are extremely many data so your O(100^2) algorithm cannot handle it. You need to do it by O(100).

(My O(100) Program runs in 0.414 sec, so when the constant factor is doubled it will time out.)