## 478 - Points in Figures: Rectangles, Circles, Triangles

Moderator: Board moderators

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### 478:Points in Figures:Rectangles,Circles and Triangles

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]
Last edited by popel on Mon Jun 10, 2002 3:17 pm, edited 1 time in total.
cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi!

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
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### Re: Hi!

cyfra wrote: 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
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore
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..
...I was born to code...
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Area of triangle

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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
EDITED
aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore
Thx guys..
The advices are great.. I wish i thought of them earlier..

Thx
Aakash
...I was born to code...
prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm

### 478- why WA ?

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
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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
{

}``````
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
Hi guys, im having some trouble on calculating the triangle's area, any help?
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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.
regards,
nymo
sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### 478 - Points in Figures: Rectangles, Circles, Triangles

Can any1 help me with critical input and output?????
IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
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!