143 - Orchard Trees

[Pavel]

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]

3...

[MegaS]

3

[paulhryu]

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]

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]

Sorry to say, I don't think that helps much either.

[Gigi's Baby]

#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]

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]

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

[Adrian Kuegel]

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]

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]

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]

[Adrian Kuegel]

Did you remove the
cout<<i<<' '<<j<<endl;
before sending to judge?

[click xx]

yes,I removed that statement but still got WA.

[click xx]

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