How to Check if Any Three Points can Make a Triangle?
- 时间:2020-09-27 14:36:16
- 分类:网络文摘
- 阅读:94 次
How to Check if Any Three Points can Make a Triangle?
There are many ways to check if any given three points in 2D plane can make a triangle. This includes: computing the triangle area and using the line equation.

geometry
A boomerang is a set of 3 points that are all distinct and not in a straight line. Given a list of three points in the plane, return whether these points are a boomerang.
Example 1:
Input: [[1,1],[2,3],[3,2]]
Output: trueExample 2:
Input: [[1,1],[2,2],[3,3]]
Output: falseNote:
points.length == 3
points[i].length == 2
0 <= points[i][j] <= 100
Compute Triangle Area
By computing the triangle area, we know if the three points can make a triangle if the area is not zero:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: bool isBoomerang(vector<vector<int>>& points) { vector<int> a = points[0]; vector<int> b = points[1]; vector<int> c = points[2]; return ((a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1])) != 0); } }; |
class Solution { public: bool isBoomerang(vector<vector<int>>& points) { vector<int> a = points[0]; vector<int> b = points[1]; vector<int> c = points[2]; return ((a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1])) != 0); } };
Compute the Line Equation
We know that we can use to represent a line in mathematics where A = (Y0 – Y1), B = (X0 – X1), and C is a constant value. If a point (X2, Y2) satisfies that
Then it is on the line formed by points (X0,Y0) and (X1,Y1).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: bool isBoomerang(vector<vector<int>>& p) { // all 3 points must be different if (p[0] == p[1] || p[0] == p[2]) { return false; } const int A = p[0][0] - p[1][0]; const int B = p[0][1] - p[1][1]; auto C = [=](vector<int>& pt) { return A * pt[1] - B * pt[0]; }; return C(p[0]) != C(p[2]); } }; |
class Solution { public: bool isBoomerang(vector<vector<int>>& p) { // all 3 points must be different if (p[0] == p[1] || p[0] == p[2]) { return false; } const int A = p[0][0] - p[1][0]; const int B = p[0][1] - p[1][1]; auto C = [=](vector<int>& pt) { return A * pt[1] - B * pt[0]; }; return C(p[0]) != C(p[2]); } };
The above C is a inline function that computes the C constant, and syntax “[=]” captures all the values used in the function, namely A and B.
Alternatively, we can check if A B and C are on the same line by arranging the line equation e.g. y = kx + b. If three points are colinear, we know that b and k should be the same for two lines. Thus, checking the y/x should be sufficient.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: bool isBoomerang(vector<vector<int>>& points) { int m1 = 0, m2 = 0; int x1 = points[0][0]; int x2 = points[1][0]; int x3 = points[2][0]; int y1 = points[0][1]; int y2 = points[1][1]; int y3 = points[2][1]; return ((y3 - y2) * (x2 - x1) != (y2 - y1) * (x3 - x2)); } }; |
class Solution { public: bool isBoomerang(vector<vector<int>>& points) { int m1 = 0, m2 = 0; int x1 = points[0][0]; int x2 = points[1][0]; int x3 = points[2][0]; int y1 = points[0][1]; int y2 = points[1][1]; int y3 = points[2][1]; return ((y3 - y2) * (x2 - x1) != (y2 - y1) * (x3 - x2)); } };
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:How to Reverse Words in a String? Design a Logger Rate Limiter in C++/Java C++ Coding Exercise: Smallest Range of Array Coding For Profit: 4 Types Of Websites To Consider Building How to Compute the Projection Area of 3D Shapes? How To Find The Ideal Monitor For Coders? How to Partition an Array Into Three Parts With Equal Sum? Compute the Sum of Even Numbers After Queries How to Compute Nested List Weight Sum of Any Arrays? 7 Laws Every Blogger Must Know to Avoid Lawsuits
- 评论列表
-
- 添加评论