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) —
推荐阅读:紫薯和红薯的营养保健价值比较 秋季5种润秋燥的美味水果最养人 揭秘6种既廉价又抗癌的美味零食 汤泡饭危害大 易导致消化机能减退 豆浆营养又美味但有6个食用禁忌 食用菌蘑菇的营养价值和保健功效 甘薯(红薯)的营养价值及保健功效 吃中秋月饼有三个较好的搭配食物 经常食用新鲜西红柿的10大益处 在感冒发烧时应该如何安排饮食
- 评论列表
-
- 添加评论