478 - Points in Figures: Rectangles, Circles, Triangles

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

478:Points in Figures:Rectangles,Circles and Triangles

Post by 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]
:roll:
...code has been removed...
:o
[/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!

Post by 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 - :wink:

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

Re: Hi!

Post by popel »

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

8)

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by 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..
...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:

Post by 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Area of triangle

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

EDITED

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by aakash_mandhar »

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

Thx
Aakash :D
...I was born to code...

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

478- why WA ?

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

Post by 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
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson »

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
Location: TORONTO, CANADA

Post by 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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by 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.
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

Post by sakhassan »

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

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

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

Post Reply

Return to “Volume 4 (400-499)”