# [Not using cross product] Easy understanding solution with explanation.

• I didn't know about the cross product as the same as some of you.
The program is a bit lengthy, but the idea is simple.
Lots of lines the code is just the flip side the other logic.
We can shorten the code significantly by joining some logic , but I think it's more clear to discuss each case separately.

``````/*
Observation:

1. Every 3 points can either form a line or a triangle, but never a concave polygon
2. Clockwise or counter-clockwise matters.
In the question's example, [[0,0],[0,10],[10,10],[10,0],[5,5]],
these 3 consecutive points break the convex rule, [10,0], [5,5], [0,0]
They break the convex rule because the points given are in clockwise.
If these 3 points were in a counter-clockwise sequence, such as in [10,0],[5,5],[0,0],[0,-5],[10,-5],
it is indeed a valid convex a polygon.

Alogrithm:
1. We pick any 3 consecutive given points, find whether we should go clockwise or counter-clockwise
with these 3 points to make them part of a convex polygon.
2. Then use the conclusion from step 1(clock or counter-clock) to check all other 3 consecutive points.
If all 3 points group can form a convex using the same order, return true, otherwise return false
*/

public class Solution {
public boolean isConvex(List<List<Integer>> points) {
if(points == null || points.size() < 3) return false;
/*Determine whehther we should try to go in clock or conter-clock wise*/
boolean clock = checkPoints(points.get(points.size() - 2), points.get(points.size() - 1), points.get(0), true);

/*check the sequence form by last poitns in the last and first 2 points in the list*/
if(!checkPoints(points.get(points.size() - 1), points.get(0), points.get(1), clock)) return false;

/*check the rest of points*/
for(int i = 2; i < points.size(); i++){
if(!checkPoints(points.get(i-2), points.get(i-1), points.get(i), clock)) return false;
}
return true;
}

/*checks whether the 3 given points can form a convex shape based on given order(clock or counter-clock)*/
public boolean checkPoints(List<Integer> p1, List<Integer> p2, List<Integer> p3, boolean clk){
/*if first 2 points has the same x value*/
if(p2.get(0) - p1.get(0) == 0){
/*p2's y is greater than p1's y, meaning we are going uphill*/
if(p2.get(1) > p1.get(1)){
/*if going clockwise, p3 should be on the right of p1 and p2,
if going counter-clockwise, p3 should be on the left of p1 and p2 */
if((clk && p3.get(0) >= p2.get(0)) || (!clk && p3.get(0) <= p2.get(0))) {
return true;
}else{
return false;
}
/*flip side*/
}else{
if((clk && p3.get(0) <= p2.get(0)) || (!clk && p3.get(0) >=  p2.get(0))){
return true;
}else{
return false;
}
}
}
/*if the first 2 points has the same y value, similar logic as above*/
if(p2.get(1) - p1.get(1) == 0){
if(p2.get(0) > p1.get(0)){
if( (clk &&p3.get(1) <= p2.get(1)) || (!clk && p3.get(1) >= p2.get(1))) {
return true;
}else{
return false;
}
}else{
if( (clk && p3.get(1) >= p2.get(1)) || (!clk && p3.get(1) <= p2.get(1))){
return true;
}else{
return false;
}
}
}

/*p1 and p2's x and y value are different, calulate the line formular formed by p1 and p2
y = m * x + n*/
double m = ((double)(p2.get(1) - p1.get(1))) / (p2.get(0) - p1.get(0));
double n = (p1.get(0) == 0 && p1.get(1) == 0) ?p2.get(1) - m * p2.get(0) : p1.get(1) - m * p1.get(0);
/*If going clockwise*/
if(clk){
/*if p3 is on the right side of p1, no matter whether the slope is positive or negative,
plug in p3's x value to the line formula, p3's y value should be smaller than that*/
if(p2.get(0) > p1.get(0)) {
return ( (m * p3.get(0) + n) >= p3.get(1));
}else{
return ( (m * p3.get(0) + n) <= p3.get(1));
}
/*flip of the logic*/
}else{
if(p2.get(0) > p1.get(0)) {
return ( (m * p3.get(0) + n) <= p3.get(1));
}else{
return ( (m * p3.get(0) + n) >= p3.get(1));
}
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.