## 143 - Orchard Trees

Moderator: Board moderators

## Should the judge tell us which test cases are messing us up?

Yes
17
52%
No
16
48%

Pavel
New poster
Posts: 2
Joined: Tue Feb 05, 2002 2:00 am
Hello,

what's the right answer when all vertices are lying in a line?

For example if the input is 1 1 2 1 3 1, what's the right output? Is it 0 or 3?

Thanks,
Pavel

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
3...

MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am
3

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### 143 - Orchard Trees

I have problems with number 143 and I think this is going to kill me if I don't get any help. I've tried like 40 different methods, with WA EVERY TIME! PLEASE HELP...

Code: Select all

// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID:  17243NT  143  C++ */

// Send to judge@uva.es

#include <fstream.h>
#include <iostream.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

#define ERROR 0.00001
#define less(a, b) ((b - a) > ERROR)
#define equal(a, b) (!less(a, b) && !less(b, a))

typedef struct {
double x;
double y;
} Point;

// Taken from http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
int cn_PnPoly(Point P, Point V[], int n) {
int cn = 0;

for(int i = 0; i < n; i++) {
if((!less(P.y, V[i].y) && less(P.y, V[i + 1].y))
|| (less(P.y, V[i].y) && !less(P.y, V[i + 1].y))) {
double vt = (P.y - V[i].y) / (V[i + 1].y - V[i].y);

if(less(P.x, V[i].x + vt * (V[i + 1].x - V[i].x)))
++cn;
}
}

return (cn & 1);
}

int main() {
Point tri[4], pt;
int count;

for(;;) {
ins >> tri[0].x >> tri[0].y >> tri[1].x >> tri[1].y >>
tri[2].x >> tri[2].y;

if(equal(tri[0].x, 0) && equal(tri[0].y, 0)
&& equal(tri[1].x, 0) && equal(tri[1].y, 0)
&& equal(tri[2].x, 0) && equal(tri[2].y, 0)) break;

tri[3] = tri[0];
count = 0;

for(pt.x = 1; pt.x <= 99; pt.x++)
for(pt.y = 1; pt.y <= 99; pt.y++) {
if(cn_PnPoly(pt, tri, 3))
count++;
}

outs << count << endl;
}

return 0;
}

// @END_OF_SOURCE_CODE

AND MY (one of 5) OTHER PROGRAM:
// @BEGIN_OF_SOURCE_CODE

/* @JUDGE_ID:  17243NT  143  C++ */

// Send to judge@uva.es

#include <fstream.h>
#include <iostream.h>

#ifdef ONLINE_JUDGE
#define ins cin
#define outs cout
#else
#define ins fin
#define outs fout
ifstream fin("myprog.in");
ofstream fout("myprog.out");
#endif

#define ERROR 0.00000001
#define less(a, b) ((b - a) > ERROR)
#define equal(a, b) (!less(a, b) && !less(b, a))

double cx, cy;

bool sideline(double x1, double y1, double x2, double y2, int x, int y) {
double v, cv, ev;

// This is the value for points on the line
ev = (y1 - y2) * x1 + (x2 - x1) * y1;

// Value for the point in question
v = (y1 - y2) * x + (x2 - x1) * y;

// Value for the point known to be on the right side of the line
cv = (y1 - y2) * cx + (x2 - x1) * cy;

// Point is on line
if(equal(v, ev)) return true;

// Both on the lesser side
if(less(cv, ev) && less(v, ev))
return true;

// Both on the greater side
if(less(ev, cv) && less(ev, v))
return true;

return false;
}

int main() {
double x1, y1, x2, y2, x3, y3;
int count, x, y;

while(fin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
if(equal(x1, 0) && equal(x2, 0) && equal(x3, 0) && equal(y1, 0)
&& equal(y2, 0) && equal(y3, 0)) break;

// The centroid of a triangle will always be in its interior
cx = (x1 + x2 + x3) / 3;
cy = (y1 + y2 + y3) / 3;

count = 0;

for(x = 1; x <= 99; x++)
for(y = 1; y <= 99; y++)
if(sideline(x1, y1, x2, y2, x, y) &&
sideline(x2, y2, x3, y3, x, y) &&
sideline(x3, y3, x1, y1, x, y))
count++;

outs << count << endl;
}

return 0;
}

// @END_OF_SOURCE_CODE

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Taken from: http://astronomy.swin.edu.au/~pbourke/g ... nsidepoly/

Here is a clean implementation:

Code: Select all

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon[0];
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}

if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
}

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
Sorry to say, I don't think that helps much either.

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

### My Program got WA. Why? Could you help me?

#include<fstream.h>
#include<math.h>

double err=1e-6;

double com_s(double x1,double y1,double x2,double y2,double x3,double y3)
{return(fabs(x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1)/2);
}

void main()
{double x[3],y[3];
double tots,s1,s2,s3;
int i,j,tot;

for( ; ; )
{cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2];
if(x[0]+x[1]+x[2]+y[1]+y[2]+y[0]==0) break;
tots=com_s(x[0],y[0],x[1],y[1],x[2],y[2]);
tot=0;
for(i=1;i<=99;i++)
for(j=1;j<=99;j++)
{s1=com_s(i,j,x[1],y[1],x[2],y[2]);
s2=com_s(i,j,x[0],y[0],x[2],y[2]);
s3=com_s(i,j,x[0],y[0],x[1],y[1]);
if(fabs(s1+s2+s3-tots)<err) tot++;
}
cout.width(4);
cout<<tot<<endl;
}
}

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
well, i just got accepted for this problem and i can tell you that with some careful analysis of conditions it can be done despite its low acceptance rate. Make sure that if a point is equal to one of the triangles coordinates then it is counted, etc.

Fireball
New poster
Posts: 3
Joined: Wed Apr 24, 2002 3:24 pm
Location: MUNICH!
Contact:

to the guys which got a accepted:

what cases must the algorithm solve?

samples:

small triangle with no tree inside.
triangle lying on the border.
all three points lie on one point.
all three points lie on a line.
clockwise triangle.
counter-clockwise triangle.

what else?

G. Ehrenstein

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I didn't made all of these special cases, just used epsilon = 1.0e-9 for calculation, for example determine the smallest value of x, rounded to higher integer:
ceil(minx-epsilon).

Fireball
New poster
Posts: 3
Joined: Wed Apr 24, 2002 3:24 pm
Location: MUNICH!
Contact:
Thx... but now i got my accepted...

my Problem where the special cases on the borders...

it took about 20-30 Submissions... but now everything is fine

cu

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am

I've submitted for many times and always got WA.
Who can give me some test data?Thanks!
Here is my program:
[cpp]#include<iostream.h>
#include<math.h>

const double esp=1e-10;

double tri[3][2];
int stx,sty,edx,edy;

double min(const double x1,const double x2)
{
return x1-x2<esp ? x1 : x2;
}

double max(const double x1,const double x2)
{
return x1-x2>-esp ? x1 : x2;
}

double multi(const double x0,const double y0,const double x1,const double y1,const double x2,const double y2)
{
return (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
}

int inside(int x,int y)
{
int i,i1,i11;
double flag1,flag2;
for(i=0;i<3;i++)
{
i1=(i==2 ? 0 : i+1);
i11=(i1==2 ? 0 : i1+1);
flag1=multi(tri[0],tri[1],tri[i1][0],tri[i1][1],tri[i11][0],tri[i11][1]);
flag2=multi(tri[0],tri[1],tri[i1][0],tri[i1][1],x,y);
if(fabs(flag1)<esp)
{
if(fabs(flag2)<esp&&x-min(min(tri[0],tri[i1][0]),tri[i11][0])>-esp&&x-max(max(tri[0],tri[i1][0]),tri[i11][0])<esp&&
y-min(min(tri[1],tri[i1][1]),tri[i11][1])>-esp&&y-max(max(tri[1],tri[i1][1]),tri[i11][1])<esp)
return 1;
return 0;
}else if(flag1*flag2<-esp)
return 0;
}
return 1;
}

int judge()
{
int i,j;
int res=0;
for(i=stx;i<=edx;i++)
{
for(j=sty;j<=edy;j++)
{
if(inside(i,j))
{
res++;
// cout<<i<<' '<<j<<endl;
}
}
}

return res;
}

int main()
{
int i,j,k;
int cinish=0;
int res;
int special;
double temp;
while(1)
{
cinish=1;
stx=sty=edx=edy=-1;
special=0;
for(i=0;i<3;i++)
{
for(j=0;j<2;j++)
{
cin>>tri[j];
if(fabs(tri[j])>esp)
cinish=0;
}
for(k=0;k<i;k++)
{
if(fabs(tri[i][0]-tri[k][0])<esp&&fabs(tri[i][1]-tri[k][1])<esp)
{
special++;
break;
}
}
if(stx<0||tri[i][0]-stx<esp)
{
stx=(int)(tri[i][0]-1);
if(stx<=0)
stx=1;
}
if(edx<0||tri[i][0]-edx>-esp)
{
edx=(int)(tri[i][0]+1);
if(edx>=100)
edx=99;
}
if(sty<0||tri[i][1]-sty<esp)
{
sty=(int)(tri[i][1]-1);
if(sty<=0)
sty=1;
}
if(edy<0||tri[i][1]-edy>-esp)
{
edy=(int)(tri[i][1]+1);
if(edy>=100)
edy=99;
}
}
if(cinish)
break;
if(special==2)
{
if(tri[0][0]>esp&&tri[0][0]-100<-esp&&tri[0][1]>esp&&tri[0][1]-100<-esp&&fabs(tri[0][0]-((int)tri[0][0]))<esp&&fabs(tri[0][1]-((int)tri[0][1]))<esp)
res=1;
else
res=0;
}else{
if(special==1&&fabs(tri[0][0]-tri[1][0])<esp&&fabs(tri[0][1]-tri[1][1])<esp)
{
temp=tri[1][0];
tri[1][0]=tri[2][0];
tri[2][0]=temp;
temp=tri[1][1];
tri[1][1]=tri[2][1];
tri[2][1]=temp;
}
res=judge();
}
cout.fill(' ');
cout.width(4);
cout<<res<<endl;
}
return 1;
}
[/cpp]
Last edited by click xx on Sat Jun 22, 2002 6:26 am, edited 1 time in total.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Did you remove the
cout<<i<<' '<<j<<endl;
before sending to judge?

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am
yes,I removed that statement but still got WA.

click xx
New poster
Posts: 10
Joined: Mon May 13, 2002 9:42 am
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!!