478 - Points in Figures: Rectangles, Circles, Triangles

[popel]

Hello Everyone,
Is there any tricks in this problem ?
I think my algorithm ok,so what causes it WA?
I have checks for point circles,triangles and rectangles.
Can anyone give me some critical test inputs ?
and check the code below please.....
[c]

...code has been removed...

[/c]

[cyfra]

Hi!

I got your program Accepted without any changes....


You'd better change your e-mail client ( or look into other topics where it is wriiten which one you should use)

Good Luck -

[popel]

I got your program Accepted without any changes....

Thank you to show me the right path. As I became sure
that the program is correct.
...And as the others my problem was also line breaking in mailer..

[aakash_mandhar]

Hi there
I got 476 and 477 accepted. but in 478 i am kinda stuck with ow to check if a pt lies in the triangle or not... Any suggestions guys..

[Larry]

A point is inside a triangle if it's left of all three lines, or right of all three lines.

You can do this by checking the sign of the cross product..

[sohel]

To identify whether a point is inside a triangle:

form three other triangles; each having the considered point as one of the vertices. Add the sum of the area of these three triangles. If it is equal to the area of the original then the point is inside the triangle ; no otherwise.

Mathematically : Let ABC be the original traingle and P the point.

if Area of ( PAB + PAC + PBC ) == Area of ABC then inside
else outside.

Hope it helps.

[shamim]

EDITED

[aakash_mandhar]

Thx guys..
The advices are great.. I wish i thought of them earlier..

Thx
Aakash

[prince56k]

i got AC on 476,477 but WA in 478. don't find any critical I/O that doesn't handle my program. could any one help me to find out the bug?

Code: Select all

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

struct rectange{	float lx,ly,rx,ry;	}rec[10];
struct circle{	float x,y,r;	}cir[10];
struct triange{	float x1,y1,x2,y2,x3,y3;	}t[10];

float area_t(float x1,float y1,float x2,float y2,float x3,float y3)
{
	float area;
	area=0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
	if(area<0.0)	area=-area;
	return area;
}

int main()
{
	char ch[5];
	int i ,j,n,p=1,flag;
	float x,y,x1,y1,x2,y2,temp,a,area,area1,area2,area3,total;
	n=0;
	while(2)
	{
			scanf("%s",&ch);
			if(ch[0]=='*')	break;
			else if(ch[0]=='r')
			{
				scanf("%f%f%f%f",&x1,&y1,&x2,&y2);
				if(x1>x2){temp=x1,x1=x2,x2=temp;}
				if(y1>y2){temp=y1,y1=y2,y2=temp;}
				rec[n].lx=x1,  rec[n].ly=y1,  rec[n].rx=x2,  rec[n].ry=y2;
				n++;
			}
			else if(ch[0]=='c'){	scanf("%f%f%f",&cir[n].x,&cir[n].y,&cir[n].r); n++;	}	
			else if(ch[0]=='t')
			{
				scanf("%f%f%f%f%f%f",&t[n].x1,&t[n].y1,&t[n].x2,&t[n].y2,&t[n].x3,&t[n].y3);
				n++;
			}
	}
	while(scanf("%f%f",&x,&y)==2)
	{
		flag=0;
		if((x>=9999.90)&&(y>=9999.90))	break;
		for(i=0;i<n;i++)
		{
			
				if((x>=rec[i].lx&&x<=rec[i].rx)&&(y>=rec[i].ly && y<=rec[i].ry))				
				{	printf("Point %d is contained in figure %d\n",p,i+1);	flag=1;	}
			
				a=sqrt((x-cir[i].x)*(x-cir[i].x)+(y-cir[i].y)*(y-cir[i].y));				
				if(a<=cir[i].r)	
				{
					printf("Point %d is contained in figure %d\n",p,i+1);
					flag=1;
				}
			
				if((int)t[i].x1==(int)t[i].x2==(int)t[i].x3==(int)t[i].y1==(int)t[i].y2==(int)t[i].y3)
					continue;
				area=area_t(t[i].x1,t[i].y1,t[i].x2,t[i].y2,t[i].x3,t[i].y3);
				area1=area_t(x,y,t[i].x2,t[i].y2,t[i].x3,t[i].y3);
				area2=area_t(t[i].x1,t[i].y1,x,y,t[i].x3,t[i].y3);
				area3=area_t(t[i].x1,t[i].y1,t[i].x2,t[i].y2,x,y);
				total=area1+area2+area3;
				if(area==total)
				{
					printf("Point %d is contained in figure %d\n",p,i+1);
					flag=1;
				}	
		}
		if(flag==0)	printf("Point %d is not contained in any figure\n",p);
		p++;
	}
	return 0;
}

[A1]

First make your three triangle area absolute.(use fabs())
Then Use it:

Code: Select all

total=area1+area2+area3;
if(total-area<=0.00001)   //epsilon=.000001 is for miscalculation
{
     
}

I hope it will help you

[Jemerson]

Hi guys, im having some trouble on calculating the triangle's area, any help?

[daveon]

Hi,
The formula can be found all over the net.

Code: Select all

#include <math.h>

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

[nymo]

Let there be two directed line segments p0p1 and p1p2 and we wish to find whether they turn left or right at point p1. This is equivalent to answering which way the angle p0p1p2 turns. We can find these answers computing CROSS PRODUCT of the VECTORS (p2 - p0) and (p1 - p0), i.e. (p2 - p0) X (p1 - p0). daveon shows how to use this and make sure you check whether all are in the left sides of edges or all are in the right sides(Larry's reply). In both cases, the point is inside the triangle. You can also check if the given point is colinear to an edge, i.e. when the area is 0.

[sakhassan]

Can any1 help me with critical input and output?????

[IRA]

It is not critical input.....
I don't know what method that you do.
You can calculate the area to find if the node is in triangle.
The area difference below 10^-6 or 10^-7 is enough!