CDFI3 - Editorial

Problem Link

Contest

Difficulty

MEDIUM

Prerequisites

Check if a point lies inside a triangle

Quick Explination

Find areas of the three triangles formed by the given points and the origin and check if their sum matches the area of outer triangle.

Explination

To check if the origin lies inside the triangle formed by the given coordinates, we need to find the area of the traingles formed by the three triangles i.e. the triangles formed by any two of the given triangles and the origin and check if the sum of these three areas equals the area of triangle formed by the given three coordinates.You can refer to Check whether a given point lies inside a triangle or not.

There is only a single corner condition in the problem when all the three coordinates are on the origin.
In this case although the three points do not form a triangle but according to the problem statement the answer for this condition will be YES.
Given below is the solution to the problem in C++


#include
#include

using namespace std;

double areac(int x1,int y1,int x2,int y2,int x3,int y3)
{
	return fabs((x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0);
}
bool inside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
	double A = areac (x1, y1, x2, y2, x3, y3);
	/* Calculate area of triangle PBC */  
   double A1 = areac (x, y, x2, y2, x3, y3);
 
   /* Calculate area of triangle PAC */  
   double A2 = areac (x1, y1, x, y, x3, y3);
 
   /* Calculate area of triangle PAB */   
   double A3 = areac (x1, y1, x2, y2, x, y);
   
   return (A == A1 + A2 + A3);
}
int main()
{
	int x1,y1,x2,y2,x3,y3;

	cin>>x1>>y1;
	cin>>x2>>y2;
	cin>>x3>>y3;
	
	double m1 = (((double)(y2 - y1))/((double)(x2 - x1)));
	double m2 = (((double)(y3 - y1))/((double)(x3 - x1)));
	double m3 = (((double)(y3 - y2))/((double)(x3 - x2)));
	if(m1 != m2)
	{
		bool ans = inside(x1,y1,x2,y2,x3,y3,0,0);
		
		if(ans==true)
		cout<<"Yes";
                else
                cout<<"No";
        }
    else
    cout<<"Invalid Input";
    return 0;
}