478  Points in Figures: Rectangles, Circles, Triangles
Moderator: Board moderators
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]
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.
Re: Hi!
Thank you to show me the right path. As I became surecyfra wrote: I got your program Accepted without any changes....
that the program is correct.
...And as the others my problem was also line breaking in mailer..

 New poster
 Posts: 38
 Joined: Thu Dec 11, 2003 3:40 pm
 Location: Bangalore
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.
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.

 New poster
 Posts: 38
 Joined: Thu Dec 11, 2003 3:40 pm
 Location: Bangalore
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*(y2y3)+x2*(y3y1)+x3*(y1y2));
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((xcir[i].x)*(xcir[i].x)+(ycir[i].y)*(ycir[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;
}
First make your three triangle area absolute.(use fabs())
Then Use it:
I hope it will help you
Then Use it:
Code: Select all
total=area1+area2+area3;
if(totalarea<=0.00001) //epsilon=.000001 is for miscalculation
{
}
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!
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
Hi,
The formula can be found all over the net.
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((x1x0)*(y2y0)(x2x0)*(y1y0));
}
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
nymo
478  Points in Figures: Rectangles, Circles, Triangles
Can any1 help me with critical input and output?????