You are not logged in. Please login at www.codechef.com to post your questions!

×

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<bits stdc++.h="">
#include<iostream>

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


asked 09 Nov '16, 18:37

intayush's gravatar image

3★intayush
41
accept rate: 0%

edited 07 Jun '17, 17:16

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,655
×73
×9
×1

question asked: 09 Nov '16, 18:37

question was seen: 293 times

last updated: 07 Jun '17, 17:16