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

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

Post by rongtuli »

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

Post by thomas1016 »

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

Post by thomas1016 »

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

Post by jutirain »

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 478 WA... Help...

Post by Jan »

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

Post by linux »

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

Post by jackpigman »

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 :cry: .....
Thanks for reading :D !!

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

Post by mf »

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
Location: CUET, Chittagong, Bangladesh
Contact:

Re: 478 point in triangle ?? getting WA

Post by aliahmed »

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
New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

Re: 478 - Point in Triangle

Post by Mehadi »

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

Post by atiburrahman09 »

#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????

Post by brianfry713 »

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

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

Post by smpss91148 »

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

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

Post by brianfry713 »

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

Post by smpss91148 »

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

Post Reply

Return to “Volume 4 (400-499)”