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

Moderator: Board moderators

rongtuli
New poster
Posts: 5
Joined: Fri Aug 17, 2007 4:38 am
hi newton,

it also suffers me lot. then i use area theorem to solve it

area = fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
hope it will help.
by tulip

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

### I use a different way

I use a different way

it is a kind of "Linear Programming Models"

and i have tried the data which is correct

but i still get WA

>_<

Code: Select all

``````
#include<iostream>

using namespace std;
int main(){
double rec[10][5];
double cir[10][4];
double tri[10][7];
double x,y;
char r;
int count, count2,fig,count3;;
bool in;
count=0;
count2=0;
count3=0;
int c2;
fig=1;
while(cin>>r){
if(r=='*')
break;
if(r=='r'){
cin>>rec[count][0];
cin>>rec[count][1];
cin>>rec[count][2];
cin>>rec[count][3];
rec[count][4]=fig;
fig++;
count++;}
else if(r=='c'){
cin>>cir[count2][0];
cin>>cir[count2][1];
cin>>cir[count2][2];
cir[count2][3]=fig;
count2++;
fig++;
}
else if(r=='t'){
cin>>tri[count3][0];
cin>>tri[count3][1];
cin>>tri[count3][2];
cin>>tri[count3][3];
cin>>tri[count3][4];
cin>>tri[count3][5];
tri[count3][6]=fig;
count3++;
cout<<count3<<endl;
fig++;
}

}
c2=0;
while(cin>>x>>y){
if(x==9999.9 && y==9999.9)
break;
c2++;
in=1;
for(int k=0;k<count;k++){

//   cout<<rec[k][0]<<'\t'<<rec[k][2]<<'\t'<<rec[k][1]<<'\t'<<rec[k][3]<<endl;
if(rec[k][0]<x && rec[k][2]>x && rec[k][1]>y && rec[k][3]<y){

cout<<"Point "<<c2<<" is contained in figure "<<rec[k][4]<<endl;
in=0;
}

}
for(int k=0;k<count2;k++){

//   cout<<rec[k][0]<<'\t'<<rec[k][2]<<'\t'<<rec[k][1]<<'\t'<<rec[k][3]<<endl;
if( (cir[k][0]-x)*(cir[k][0]-x)+(cir[k][1]-y)*(cir[k][1]-y) < cir[k][2]*cir[k][2] ){

cout<<"Point "<<c2<<" is contained in figure "<<cir[k][3]<<endl;
in=0;
}

}

for(int k=0;k<count3;k++){

if(   (      (  (tri[k][1]-tri[k][3])*(tri[k][2]-x)/(tri[k][0]-tri[k][2]) -tri[k][3]+y )   *     (  (tri[k][1]-tri[k][3])*(tri[k][2]-tri[k][4])/(tri[k][0]-tri[k][2]) -tri[k][3]+tri[k][5] )                           ) >0    &&     ( (  (tri[k][5]-tri[k][3])*(tri[k][2]-x)/(tri[k][4]-tri[k][2]) -tri[k][3]+y )   *     (  (tri[k][5]-tri[k][3])*(tri[k][2]-tri[k][0])/(tri[k][4]-tri[k][2]) -tri[k][3]+tri[k][1] )                           ) >0  &&    (      (  (tri[k][5]-tri[k][1])*(tri[k][3]-x)/(tri[k][4]-tri[k][0]) -tri[k][1]+y )   *     (  (tri[k][5]-tri[k][1])*(tri[k][3]-tri[k][2])/(tri[k][4]-tri[k][0]) -tri[k][1]+tri[k][3] )                           ) >0    ){

cout<<"Point "<<c2<<" is contained in figure "<<tri[k][6]<<endl;
in=0;

}
}
if(in){

cout<<"Point "<<c2<<" is not contained in any figure"<<endl;

}

}
// system("pause");
return 0;
}

``````

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm
I modify my code

it is WA because of the sequence of figure

Code: Select all

``````
#include<iostream>

using namespace std;
int main(){
double rec[10][5];
double cir[10][4];
double tri[10][7];
bool fi[11];
double x,y;
char r;
int count, count2,fig,count3;;
bool in;
count=0;
count2=0;
count3=0;
int c2;
fig=1;
while(cin>>r){
if(r=='*')
break;
if(r=='r'){
cin>>rec[count][0];
cin>>rec[count][1];
cin>>rec[count][2];
cin>>rec[count][3];
rec[count][4]=fig;
fig++;
count++;}
else if(r=='c'){
cin>>cir[count2][0];
cin>>cir[count2][1];
cin>>cir[count2][2];
cir[count2][3]=fig;
count2++;
fig++;
}
else if(r=='t'){
cin>>tri[count3][0];
cin>>tri[count3][1];
cin>>tri[count3][2];
cin>>tri[count3][3];
cin>>tri[count3][4];
cin>>tri[count3][5];
tri[count3][6]=fig;
count3++;

fig++;
}

}
c2=0;
while(cin>>x>>y){
fi[0]=0;
fi[1]=0;
fi[2]=0;
fi[3]=0;
fi[4]=0;
fi[5]=0;
fi[6]=0;
fi[7]=0;
fi[8]=0;
fi[9]=0;
fi[10]=0;
if(x==9999.9 && y==9999.9)
break;
c2++;
in=1;
for(int k=0;k<count;k++){

if(rec[k][0]<x && rec[k][2]>x && rec[k][1]>y && rec[k][3]<y){

fi[(int)(rec[k][4])]=1;
in=0;
}

}
for(int k=0;k<count2;k++){

if( (cir[k][0]-x)*(cir[k][0]-x)+(cir[k][1]-y)*(cir[k][1]-y) < cir[k][2]*cir[k][2] ){
fi[(int)cir[k][3]]=1;

in=0;
}

}

for(int k=0;k<count3;k++){

if(   (      (  (tri[k][1]-tri[k][3])*(tri[k][2]-x)/(tri[k][0]-tri[k][2]) -tri[k][3]+y )   *     (  (tri[k][1]-tri[k][3])*(tri[k][2]-tri[k][4])/(tri[k][0]-tri[k][2]) -tri[k][3]+tri[k][5] )                           ) >0    &&     ( (  (tri[k][5]-tri[k][3])*(tri[k][2]-x)/(tri[k][4]-tri[k][2]) -tri[k][3]+y )   *     (  (tri[k][5]-tri[k][3])*(tri[k][2]-tri[k][0])/(tri[k][4]-tri[k][2]) -tri[k][3]+tri[k][1] )                           ) >0  &&    (      (  (tri[k][5]-tri[k][1])*(tri[k][3]-x)/(tri[k][4]-tri[k][0]) -tri[k][1]+y )   *     (  (tri[k][5]-tri[k][1])*(tri[k][3]-tri[k][2])/(tri[k][4]-tri[k][0]) -tri[k][1]+tri[k][3] )                           ) >0    ){

fi[(int)tri[k][6]]=1;
in=0;

}
}
if(in){

cout<<"Point "<<c2<<" is not contained in any figure"<<endl;

}
else{
for(int k=0;k<11;k++){
if(fi[k]==1)
cout<<"Point "<<c2<<" is contained in figure "<<k<<endl;
}

}

}
// system("pause");
return 0;
}

``````

jutirain
New poster
Posts: 1
Joined: Tue Sep 09, 2008 1:09 pm

### 478 WA... Help...

I've past 476 and 477 easily, but got several WA in 478...

I'm using (area(PAB) + area(PAC) + area(PBC) - area(ABC) < EPS) to judge if a point inside the triangle. Here's my code of critical session:

Code: Select all

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

bool compare_point_with_triangle(Point point, Triangle triangle)
{
double sub_area_1 = triangle_area(point.x, point.y, triangle.x1, triangle.y1, triangle.x2, triangle.y2);
double sub_area_2 = triangle_area(point.x, point.y, triangle.x2, triangle.y2, triangle.x3, triangle.y3);
double sub_area_3 = triangle_area(point.x, point.y, triangle.x1, triangle.y1, triangle.x3, triangle.y3);
double original_area = triangle_area(triangle.x1, triangle.y1, triangle.x2, triangle.y2, triangle.x3, triangle.y3);
if(fabs(sub_area_1 + sub_area_2 + sub_area_3 - original_area) < 0.001)
return true;
else
return false;
}
``````
Any idea or some critical input data?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 478 WA... Help...

Search the board first. Use an existing thread.
Ami ekhono shopno dekhi...
HomePage

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### Re: 478 point in triangle ?? getting WA

Newton wrote:
i tried but cant find the bug. please help me where is my faults. why this code does not give me write output???
In problem description,
The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9
So

Code: Select all

``````          if(x > 9999.8 && y > 9999.8)
break;
``````
is not valid. Use like this:

Code: Select all

``````#include <cstdlib>
if(fabs(x - 9999.9)<EPS && fabs(y - 9999.9)<EPS)
break;
``````
To be more precise consider some more cases:
In prob desc,
Points coinciding with a figure border are not considered inside.
So consider,
When a point is on the boundary of circle which means coincides what will your code do? It might fail.
Prob desc,
For a rectangle, there will be four real values designating the x-y coordinates of the upper left and lower right corners.
For example given points (x1, y1) and (x2,y2)
I am not sure if x1>x2 always! So it's better to check like this

Code: Select all

``````If (x1<x2) {
if (x1<x<x2) {
// point is inside
}
}
else if (x1>x2) {
if (x1<x<x2) {
// point is inside
}
}
else {
// point is not inside
}
``````
Solving for fun..

jackpigman
New poster
Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm

### Re: 478 point in triangle ?? getting WA

Keep getting WA's, can anybody help me?
I'm pretty sure the bug's in the triangle part, but just can't find it .....

Code: Select all

``````AC
``````
Last edited by jackpigman on Wed Apr 08, 2009 7:25 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 478 point in triangle ?? getting WA

Did you even try testing your program on the sample input/output? I've tried to run it, and here's a snippet of what it printed:

Code: Select all

``````Point 1 is contained in figure 3
Point 1 is contained in figure 4
Point 1 is contained in figure 6
Point 1 is contained in figure 9
Point 2 is contained in figure 3
Point 2 is contained in figure 4
Point 2 is contained in figure 6
Point 2 is contained in figure 7
Point 2 is contained in figure 9
Point 3 is contained in figure 3
...
``````

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Contact:

### Re: 478 point in triangle ?? getting WA

Getting WA

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

int main()
{
double x1[15][2],x2[15],y1[15],y2[15],c1[15][2],c2[15],r[15],tx1[15][2],tx2[15],tx3[15],ty1[15],ty2[15],ty3[15],d,x,y,s,a,b,cc,a1,a2,a3,a4,m1,m2,m3;
long i=0,j=0,k=0,c=1, f, point=1, flag ,co=0;
char ch;

scanf("%c",&ch);
while(1)
{
if(ch=='*')
break;
if(ch=='r')
{
scanf("%lf%lf%lf%lf",&x1[0],&y1,&x2,&y2);

x1[1]=c++;
i++;
}
else if(ch=='c')
{
scanf("%lf%lf%lf",&c1[j][0],&c2[j],&r[j]);
c1[j][1]=c++;

j++;

}
else if(ch=='t')
{
scanf("%lf%lf%lf%lf%lf%lf",&tx1[k][0],&ty1[k],&tx2[k],&ty2[k],&tx3[k],&ty3[k]);
tx1[k][1]=c++;

k++;
}
getchar();
scanf("%c",&ch);
}

while(scanf("%lf%lf",&x,&y),x!=9999.9 , y!=9999.9)
{

flag=0;

for(f=0; f<i; f++)
{
co=1;
if(((x2[f]>=x && x1[f][0]<=x) || (x1[f][0]>=x && x2[f]<=x)) && ((y2[f]>=y && y1[f]<=y) || (y1[f]>=y && y2[f]<=y)))
{

printf("Point %ld is contained in figure %.lf\n",point,x1[f][1]);

flag=1;
}
}
for(f=0; f<j; f++)
{
d=sqrt(pow(fabs(c1[f][0]-x),2)+pow(fabs(c2[f]-y),2));

if(d<=r[f])
{
printf("Point %ld is contained in figure %.lf\n",point,c1[f][1]);
flag=1;
}
}

for(f=0; f<k ; f++) ////for triangle
{
cc=sqrt(pow(fabs(tx1[f][0]-tx2[f]),2)+pow(fabs(ty1[f]-ty2[f]),2));
b=sqrt(pow(fabs(tx1[f][0]-tx3[f]),2)+pow(fabs(ty1[f]-ty3[f]),2));
a=sqrt(pow(fabs(tx2[f]-tx3[f]),2)+pow(fabs(ty2[f]-ty3[f]),2));
s=(a+b+cc)/2;
a1=sqrt(s*(s-a)*(s-b)*(s-cc));

m1=sqrt(pow(fabs(tx1[f][0]-x),2)+pow(fabs(ty1[f]-y),2));
m2=sqrt(pow(fabs(tx2[f]-x),2)+pow(fabs(ty2[f]-y),2));
m3=sqrt(pow(fabs(tx3[f]-x),2)+pow(fabs(ty3[f]-y),2));
s=(m1+m2+cc)/2;
a2=sqrt(s*(s-m1)*(s-m2)*(s-cc));
s=(a+m2+m3)/2;
a3=sqrt(s*(s-a)*(s-m2)*(s-m3));
s=(m1+b+m3)/2;
a4=sqrt(s*(s-m1)*(s-b)*(s-m3));

if(fabs(a4 + a2 + a3 - a1) <= 0.000001)
{
printf("Point %ld is contained in figure %.lf\n",point,tx1[f][1]);
flag=1;
}

}

if(flag==0)
printf("Point %ld is not contained in any figure\n",point);
point++;
}

return 0;
}

New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

### Re: 478 - Point in Triangle

It's a easy Geometry Problem.
My algo:
Think the point inside the triangle ABC.so connect the point d with A,B,&C.
so there will be three such triangle.
Summation of the Area of these three triangle will be equal with Area ABC if the point is inside otherwisw outside.
Be careful about floating point Error.

atiburrahman09
New poster
Posts: 6
Joined: Mon Mar 26, 2012 10:12 pm

### 478-Why not accepting????

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
char a[500];
int i;

scanf("%s",a); /*taking input for decoding*/
for(i=0;i<strlen(a);i++)
{
a=((a-7));
}
for(i=0;i<strlen(a);i++)
printf("%c",a);

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 478-Why not accepting????

This is not even close to a solution for 478 - Points in Figures: Rectangles, Circles, Triangles.
Check input and AC output for thousands of problems on uDebug!

smpss91148
New poster
Posts: 3
Joined: Mon Jul 23, 2012 4:51 pm

I have passed 476 and 477, so I think there must be some problems in Triangle part!! Please help me find it!!

I use Vector rotation to deal with it which I saw on another site. (It is written in Chinese)http://www.csie.ntnu.edu.tw/~u91029/PointLinePlane.html

Code: Select all

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

struct shapedata
{
char type;
double dot[6];
};

struct dotdata
{
double x,y;
};

int circle(double ax,double ay,double bx,double by,struct dotdata o)
{
double temp;
temp=(ax-o.x)*(by-o.y)-(ay-o.y)*(bx-o.x);
if(temp>0)
return 1;
else if(temp==0)
return 0;
else
return -1;
}

int main(void)
{
struct shapedata shape[10];
struct dotdata dot;
char temp[10];
int i,j,a,b,c;
int s_max;
char in_if,never_if;

while(1)
{
s_max=0;
while(1)
{
if(scanf("%s",temp)==EOF)
return 0;
else if(temp[0]=='*')
break;
else
{
shape[s_max].type=temp[0];
switch(temp[0])
{
case 'r':
j=4;
break;
case 'c':
j=3;
break;
case 't':
j=6;
break;
}
for(i=0;i<j;i++)
scanf("%lf",&shape[s_max].dot[i]);
}
s_max++;
}
i=0;
while(scanf("%lf %lf",&dot.x,&dot.y)!=EOF && (dot.x!=9999.9 || dot.y!=9999.9))
{
never_if=1;
for(j=0;j<s_max;j++)
{
in_if=0;
switch(shape[j].type)
{
case 'r':
if(dot.x>shape[j].dot[0] && dot.x<shape[j].dot[2] && \
dot.y<shape[j].dot[1] && dot.y>shape[j].dot[3])
in_if=1;
break;
case 'c':
a=shape[j].dot[0]-dot.x;
b=shape[j].dot[1]-dot.y;
if(a*a+b*b<shape[j].dot[2]*shape[j].dot[2])
in_if=1;
break;
case 't':
a=circle(shape[j].dot[0],shape[j].dot[1],shape[j].dot[2],shape[j].dot[3],dot);
b=circle(shape[j].dot[2],shape[j].dot[3],shape[j].dot[4],shape[j].dot[5],dot);
c=circle(shape[j].dot[4],shape[j].dot[5],shape[j].dot[0],shape[j].dot[1],dot);
if(a==b && b==c)
in_if=1;
break;
}
if(in_if)
{
never_if=0;
printf("Point %d is contained in figure %d\n",i+1,j+1);
}
}
if(never_if)
printf("Point %d is not contained in any figure\n",i+1);
i++;
}
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

c 0.0 0.0 3.7
*
0.0 3.6
0.0 3.8
9999.9 9999.9
Check input and AC output for thousands of problems on uDebug!

smpss91148
New poster
Posts: 3
Joined: Mon Jul 23, 2012 4:51 pm

### Thank you!!

Thank you!! I have found the problem. (I changed a,b,c from int to double.)