478 - Points in Figures: Rectangles, Circles, Triangles

[sakhassan]

thanks IRa ... but i had found ma problem and got ac..
i thought i was wrong in calculating area ... though it wasnt... it was a precision error which make me crazy to getting WAAAAAAAA....
for triangle ... the point is inside the figure only when
fabs( area1 + area2 + area3 - original area) <=EPS
where EPS == .000001 i used here 1e-13 thats the reason for WA

[spider_6765]

i corrected it with EPS
still no success... can n e one help me?

Code: Select all

   thanx i got accepted

[little joey]

Code: Select all

double triangleArea(int x1,int y1,int x2,int y2,int x3,int y3){
	return fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)); 
}

How accurate do you think this function is when you feed it doubles?

[Zaspire]

I got WA! Help Please

Code: Select all

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

#define PE 0.000001

class Shape
{
public:
	virtual void read()=NULL;
	virtual bool Contain(double x,double y)=NULL;
};

class Rectangle:Shape
{
	double lx,ly,rx,ry;
public:
	void read()
	{
		scanf("%lf %lf %lf %lf",&lx,&ly,&rx,&ry);
	}
	bool Contain(double x,double y)
	{
		if ((x-lx>PE)&&(x-rx<-PE)&&(y-ry>PE)&&(y-ly<-PE)) return true;
		else return false;
	}
};

class Circle:Shape
{
	double cx,cy,r;
public:
	void read()
	{
		scanf("%lf %lf %lf",&cx,&cy,&r);
		r=r*r;
	}
	bool Contain(double x,double y)
	{
		if ((x-cx)*(x-cx)+(y-cy)*(y-cy)-r<-PE) return true;
		else return false;
	}
};

class Triangle:Shape
{
double x1,y1,x2,y2,x3,y3,t,s;
#define S(x0,y0,x1,y1,x2,y2) abs((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0))
public:
	void read()
	{
		scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3);
		s=S(x1,y1,x2,y2,x3,y3);
	}
	bool Contain(double x,double y)
	{
		double s1=S(x,y,x1,y1,x2,y2),s2=S(x,y,x2,y2,x3,y3),s3=S(x,y,x3,y3,x1,y1);
		if ((abs(s-s1-s2-s3)<PE)&&(s1>PE)&&(s2>PE)&&(s3>PE)) return true;
		else return false;
	}
};

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	Shape **store;
	store=(Shape**)malloc(sizeof(Shape*)*50);
	int col,i,k;
	char c;
	col=0;
	while (scanf(" %c",&c),c!='*')
	{
		if (c=='r') store[col]=(Shape*)new Rectangle();
		if (c=='c') store[col]=(Shape*)new Circle();
		if (c=='t')	store[col]=(Shape*)new Triangle();
		store[col]->read();
		col++;
	}
	double x,y;
	k=1;
	while (scanf("%lf %lf",&x,&y),(abs(x-9999.9)>PE)||(abs(y-9999.9)>PE))
	{
		c=0;
		for (i=0;i<col;i++)
			if (store[i]->Contain(x,y)) {printf("Point %d is contained in figure %d\n",k,i+1);c=1;}
		if (c==0) printf("Point %d is not contained in any figure\n",k);
		k++;
	}
	return 0;
}

[Jan]

Dont open a new thread if there is one already. Try to post in the existing thread.

[dipaly]

i did 476 & 477 ..so i think there is no prob..in rectangle & circle .. i solve triangle with this
whole area = area1+area2+area3
--> if(a==a1+a2+a3)

but it's not work here is my area calculating function and the checking point in triangle..

Code: Select all

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

Code: Select all

else if(ch[i]=='t')
{
				
double a1 = area(x,y,s[i][2],s[i][3],s[i][4],s[i][5]);
double a = area(s[i][0],s[i][1],s[i][2],s[i][3],s[i][4],s[i][5]);
double a2 = area(s[i][0],s[i][1],x,y,s[i][4],s[i][5]);
double a3 = area(s[i][0],s[i][1],s[i][2],s[i][3],x,y);
if(((a-a1-a2-a3)> -1) && ((a-a1-a2-a3)<=0.000001) && (a1>0.000001) && (a2>0.000001) && (a3>0.000001))
	printf("Point %d is contained in figure %d\n",m,j);
}

plzzzzzzzzzz reply
sorry 4 my poor english[/code]

[helloneo]

Why -1 here..?

Code: Select all

if(((a-a1-a2-a3)> -1) && .. 

[dipaly]

Code: Select all

if(((a-a1-a2-a3)> -1) && 

its for if (a1+a2+a3>a)
ok i change my code now it is..

Code: Select all

	else if(ch[i]=='t')
			{
				double a1 = area_t(x,y,s[i][2],s[i][3],s[i][4],s[i][5]);
				double a = area_t(s[i][0],s[i][1],s[i][2],s[i][3],s[i][4],s[i][5]);
				double a2 = area_t(s[i][0],s[i][1],x,y,s[i][4],s[i][5]);
				double a3 = area_t(s[i][0],s[i][1],s[i][2],s[i][3],x,y);
				if( ((a-a1-a2-a3)<=0.000001) && (a1>0.000001) && (a2>0.000001) && (a3>0.000001))
					printf("Point %d is contained in figure %d\n",g,j);
			}

but still WA

[dipaly]

here is my code .. help me plz

Code: Select all

deleted

[helloneo]

I think

Code: Select all

if( ((a-a1-a2-a3)<=0.000001) && 

should be

Code: Select all

if( (fabs(a-a1-a2-a3)<=0.000001) && 

[dipaly]

thanxxxxxxxxxx helloneo ac now

[newton]

i have solved 476 and 477 easily
but here is a problem with triangle.
do you think this functions works well.

Code: Select all

inline int is_in_left(LD x1,LD y1, LD x2, LD y2, LD x3, LD y3)
{
	LD area;
	area = 0.5 * (x1*(y2-1)*(y3-1) - y1*(x2-1)*(x3-1) + (x2-y3)*(x3-y2));
	if(area <= 0)
		return 0;
	else 
		return 1;
}

inline int is_inside_tri(LD x1,LD y1,LD x2,LD y2,LD x3,LD y3,LD x,LD y)
{
	int f1,f2,f3;

	f1 = is_in_left(x1,y1,x2,y2,x,y);
	f2 = is_in_left(x2,y2,x3,y3,x,y);
	f3 = is_in_left(x3,y3,x1,y1,x,y);

	if(f1 && f2 && f3)
		return 1;

	return 0;
}

advanced thanx

[emotional blind]

You have considered.. the point is in left turn for all 3 sides to being in triangle
What if all triangles are in right turn?
have you consider it?

Code: Select all

   if(f1 && f2 && f3)
      return 1; 

should it not be like this?

Code: Select all

   if(f1 && f2 && f3)
      return 1; 
   if(!(f1||f2||f3))
      return 1;

[newton]

i tried but cant find the bug. please help me where is my faults. why this code does not give me write output???

Code: Select all

#include <stdio.h>
#include <string.h>

#define LD long double

struct rect{
				char c;
				LD upp_left_x;
				LD upp_left_y;
				LD low_right_x;
				LD low_right_y;
};

struct circle{
	
				LD x0;
				LD y0;
				LD redius;
};

struct triangle{

				LD x1;
				LD y1;
				LD x2;
				LD y2;
				LD x3;
				LD y3;
};


inline int is_in_left(LD x1,LD y1, LD x2, LD y2, LD x3, LD y3)
{
	LD area;
	area = 0.5 * (x1*(y2-1)*(y3-1) - y1*(x2-1)*(x3-1) + (x2-y3)*(x3-y2));
	if(area <= 0)
		return 0;
	else 
		return 1;
}

inline int is_tri(LD x1,LD y1,LD x2,LD y2,LD x3,LD y3,LD x,LD y)
{
	int f1,f2,f3;

	f1 = is_in_left(x1,y1,x2,y2,x,y);
	f2 = is_in_left(x2,y2,x3,y3,x,y);
	f3 = is_in_left(x3,y3,x1,y1,x,y);

	if(f1 == f2 == f3) 
      return 1; 
    
	return 0;
}

int main()
{
	rect     array[100];
	circle	 cir[100];
	triangle tri[100];    

	int r ,c,k,i;
	int flag,j;
	LD x,y;
	
	r = 1;
	c = 1;
	k = 1;
	i = 1;

	while(1)
	{
		scanf(" %c",&array[i].c);

		if(array[i].c == '*')
			break;

		if(array[i].c == 'r')
			scanf("%Lf %Lf %Lf %Lf",&array[i].upp_left_x,&array[i].upp_left_y,&array[i].low_right_x,&array[i].low_right_y);

		else if(array[i].c == 'c')
			scanf("%Lf %Lf %Lf",&cir[i].x0,&cir[i].y0,&cir[i].redius);

		else if(array[i].c == 't')
			scanf("%Lf %Lf %Lf %Lf %Lf %Lf",&tri[i].x1,&tri[i].y1,&tri[i].x2,&tri[i].y2,&tri[i].x3,&tri[i].y3);
		i++;		
	}
	
	while(scanf("%Lf %Lf",&x,&y)==2)
	{
		if(x > 9999.8 && y > 9999.8)
			break;		
		flag = 1;
		for(j = 1;j < i;j++)
		{		
			if(array[j].c == 'r')
			{
				if((x > array[j].upp_left_x && x < array[j].low_right_x ) && ( y < array[j].upp_left_y && y > array[j].low_right_y))
				{
					printf("Point %d is contained in figure %d\n",k,j);
					flag = 0;
				}			
			}
			else if(array[j].c == 'c')
			{
				if((x - cir[j].x0)*(x - cir[j].x0) + (y - cir[j].y0)*(y - cir[j].y0) < cir[j].redius * cir[j].redius )
				{
					printf("Point %d is contained in figure %d\n",k,j);
					flag = 0;
				}
			
			}
			else if(array[j].c == 't')
			{
				if(is_tri(tri[j].x1,tri[j].y1,tri[j].x2,tri[j].y2,tri[j].x3,tri[j].y3,x,y))
				{
					printf("Point %d is contained in figure %d\n",k,j);
					flag = 0;
				}	
			}
		}

		if(flag)
				printf("Point %d is not contained in any figure\n",k);

		k++;
	}
	return 0;
}

advanced thanx

[andysoft]

hello..
I am posting again, because I am tired of WA, that judge gives, though I am sure my solution is OK.
I think, that it is not because of eps value...
Maybe someone may have a fresh look at it.
THANX!!

(probably, the most important part is before the global "begin": functions for the solving!)

Code: Select all

program Project2;

{$APPTYPE CONSOLE}
{$R-}{$S-}{$Q-}

uses
  SysUtils,
  Math;

const
  eps = 0.000001;

function d(const x1,y1,x2,y2: extended): extended;
begin
  result := sqrt(sqr(x1-x2)+sqr(y1-y2))
end;

function s(const a,b,c: extended): extended;
var
  p: extended;
begin
  p := (a + b + c)/2.0;
  result := sqrt (p*(p-a)*(p-b)*(p-c))
end;

function pointInCircle (const x,y,xc,yc,r: extended): boolean;
var
  rd: extended;
begin
  rd := d(x,y,xc,yc);
  result := (rd - r < 0)
end;

function pointInRectangle (const x,y,x1,y1,x2,y2: extended): boolean;
begin
  result := (x>x1) and (y<y1) and (x<x2) and (y>y2);
end;

function pointInTriangle (const x,y,x1,y1,x2,y2,x3,y3: extended): boolean;
var
  a,b,c: extended;
  a1,b1,c1: extended;
begin
  a := d(x1,y1,x2,y2);
  b := d(x1,y1,x3,y3);
  c := d(x2,y2,x3,y3);
  a1 := d(x,y,x2,y2);
  b1 := d(x,y,x1,y1);
  c1 := d(x,y,x3,y3);
  result := abs(s(a,b,c) - s(a1,c1,c) - s(a1,b1,a) - s(b1,c1,b)) < eps
end;

type
  figPoint = record
    t: char;
    ind: integer;
  end;
  circle = record
    x,y,r: extended;
  end;
  rectangle = record
    x1,y1,x2,y2: extended;
  end;
  triangle = record
    x1,y1,x2,y2,x3,y3: extended;
  end;

var
  i,j,k,l,m,n,nc,nr,nt,ci: integer;
  fig: array [1..100] of figPoint;
  cir: array [1..100] of circle;
  rec: array [1..100] of rectangle;
  tri: array [1..100] of triangle;
  x,y: extended;
  c: char;
  fl: boolean;

procedure out(const point,figure: integer);
begin
  fl := true;
  writeln ('Point ',point,' is contained in figure ',figure)
end;

begin
  n := 0;
  nr := 0;
  nc := 0;
  nt := 0;

  while true do
  begin
    read (c);
    if c = '*' then break;
    inc(n);
    fig[n].t := c;
    case c of
      'r':
      begin
        inc (nr);
        fig[n].ind := nr;
        readln (rec[nr].x1,rec[nr].y1,rec[nr].x2,rec[nr].y2)
      end;
      'c':
      begin
        inc (nc);
        fig[n].ind := nc;
        readln (cir[nc].x,cir[nc].y,cir[nc].r)
      end;
      't':
      begin
        inc(nt);
        fig[n].ind := nt;
        readln (tri[nt].x1,tri[nt].y1,tri[nt].x2,tri[nt].y2,tri[nt].x3,tri[nr].y3)
      end;
    end;
  end;
  ci := 0;
  while true do
  begin
    readln (x,y);
    if (x=9999.9) and (y=9999.9) then break;
    inc(ci);
    fl := false;
    for i:=1 to n do
      case fig[i].t of
        'c':
          if pointInCircle(x,y,cir[fig[i].ind].x,cir[fig[i].ind].y,cir[fig[i].ind].r) then
            out (ci,i);
        'r':
          if pointInRectangle(x,y,rec[fig[i].ind].x1,rec[fig[i].ind].y1,rec[fig[i].ind].x2,rec[fig[i].ind].y2) then
            out (ci,i);
        't':
          if pointInTriangle(x,y,tri[fig[i].ind].x1,tri[fig[i].ind].y1,tri[fig[i].ind].x2,tri[fig[i].ind].y2,tri[fig[i].ind].x3,tri[fig[i].ind].y3) then
            out (ci,i);
      end;
    if not fl then
      writeln ('Point ',ci,' is not contained in any figure');
  end;




end.