478 - Points in Figures: Rectangles, Circles, Triangles

rongtuli · Post by **rongtuli** » Sun Aug 26, 2007 7:09 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.

thomas1016 · Post by **thomas1016** » Sat Jan 19, 2008 7:51 pm

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 · Post by **thomas1016** » Sun Jan 20, 2008 5:19 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 · Post by **jutirain** » Tue Sep 09, 2008 1:16 pm

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?

Thanks in advance!

Jan · Post by **Jan** » Thu Sep 11, 2008 6:29 am

Search the board first. Use an existing thread.

linux · Post by **linux** » Sat Oct 18, 2008 2:10 pm

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
}

jackpigman · Post by **jackpigman** » Wed Apr 08, 2009 12:15 am

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

.....
Thanks for reading

!!

Code: Select all

AC

mf · Post by mf » Wed Apr 08, 2009 1:21 am

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 · Post by **aliahmed** » Thu Jul 16, 2009 11:45 pm

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;
}

Mehadi · Post by **Mehadi** » Fri Apr 16, 2010 12:09 pm

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 · Post by **atiburrahman09** » Mon Mar 26, 2012 10:18 pm

#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 · Post by **brianfry713** » Tue Mar 27, 2012 11:44 pm

This is not even close to a solution for 478 - Points in Figures: Rectangles, Circles, Triangles.

smpss91148 · Post by **smpss91148** » Mon Jul 23, 2012 5:01 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 · Post by **brianfry713** » Tue Jul 24, 2012 12:54 am

c 0.0 0.0 3.7
*
0.0 3.6
0.0 3.8
9999.9 9999.9

smpss91148 · Post by **smpss91148** » Fri Jul 27, 2012 7:32 am

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

OJ Board

478 - Points in Figures: Rectangles, Circles, Triangles

I use a different way

478 WA... Help...

Re: 478 WA... Help...

Re: 478 point in triangle ?? getting WA

Re: 478 point in triangle ?? getting WA

Re: 478 point in triangle ?? getting WA

Re: 478 point in triangle ?? getting WA

Re: 478 - Point in Triangle

478-Why not accepting????

Re: 478-Why not accepting????

My code of 478 can't be accepted!! Please help me!!

Re: My code of 478 can't be accepted!! Please help me!!

Thank you!!