Geometry
Ax + By + c = 0
Given: (x1, y1), (x2, y2)
A = y2 - y1
B = x1 - x2
C = A * x1 + B * y1
###Intersection of Lines
A1x + B1y + C1 = 0
A2X + B2y + C2 = 0
Quick Insight: We know that the above equations can also be treated as Vector Equations, C being the intercept which measures the perpendicular distance from the origin. If we take the determinant of the equations, it will tell us number of independent dimensions in the system. Determinant of 0 will mean the systems of equations at hand have only one independent diemension which means one vector is parallel to the other. Parallel vectors will mean lines are parallel or collinear(which is just another way of stating if the lines are parallel).
det = A1 * B2 - B1 * A2
Point of intersection:
x = (C2 * B1 - C1 * B1) / det
y = (C1 * A2 - A1 * C2) / det
With real numbers we need to be careful about float division and equality.
We can find the equations of the lines corresponding to the line segments. Find the point of intersection of lines and test whether that points lies on both the lines or not.
Orientation: Let us define three points on a plane, (A, B, C), and connect them. Now if we take out right hand, point our fingers towards the line AB(line segment from A to B) and curl our fingers towards BC, then the direction in which you curl your fingers gives the Orientation. It can be clockwise or counter clockwise. Another point to note is that the direction of the thumb can also be used just like it is used in Vector Cross Product.
long inline orientation(pair<long, long>& a, pair<long, long>& b, pair<long, long>& c) {
// Positive: Clockwise
// Negative: Counter Clockwise
// Zero: Collinear Points
return (b.second - a.second) * (c.first - b.first) -
(c.second - b.second) * (b.first - a.first);
}
It should be noted that the Orientation of the triangle can be positive or negative(if we treat the sides of the triangle as vectors). Take the three points that define the Triangle and use the above formula to calculate it. If the Orientation of a triangle is negative we can make it positive by swapping the order of the last two vertices or vice versa.
Therefore to check where a point lies inside a triangle or not we can first make the Orientation of the triangle to be positive and then the given point will lie inside the triangle if the Orientation of that point is positive with the all the edges.
Points A, B, C define the triangle and D is the given point
if Orientation(A, B, D) >= 0 && Orientation(B, C, D) >=0 &&
Orientation(C, A, D) >= 0
then the given point D lies inside the triangle.
If we remove the equality above then we will be dealing with the points which are strictly inside the triangle(points on the edge will not be considered as inside the triangle).
A convex polygon is a polygon in which the orientation of any three consecutive points clockwise or counter-clockwise will be non-negative or non-positive respectively(negative if thumb points down and positive if thumb points up).
A set of points is a Convex set if taken two points in the set, all the points on the line segment are in the set itself.
Using the formula given above for calculating the orientation, positive value means thumb pointing downwards and negative value means thumb pointing upwards.
Take the point in consideration and checks its orientation with all edges of the polygon. Edges of the polygon are considered in clockwise direction. If the orientation of the point is positive with all the edges then the point is inside the polygon. Orientation 0 means that the point is on the edge.
Time Complexity: O(n)
In order to solve this problem faster we need to understand one thing that a convex polygon can be decomposed into a disjoint set of triangles. Combining all the triangles will give us the convex hull back. The way we decompose the triangle is that we choose a pivot point and draw straight lines to the other points.
As we can see in the above figure: Polygon = ABC + ACD + ADE + AEF. A is used as the pivot point in the above polygon. It is interesting to note that checking if a point is in a polygon can be reduced to checking if the point is inside a particular triangle. And checking the presence of a point in a triangle is a constant time operation. The main trick is to use binary search to search for the triangle in which the point may lie. Here we use orientation of the point with the edges of the triangles. We can clearly see that the edges of the triangle, excluding the sides of the polygon except for the first and last triangle, divide the whole plane into discrete parts(They divide the whole 360 degrees).
Example: Line AB, AC, AD, AE, AF divide the whole plane into disjoint parts. Here we have excluded the edges of the polygon BC, CD, DE, EF except AB and AF.
Problem: Given a set of points check their presence in the Convex Polygon.
pair<ll, ll> inputA[SIZE];
pair<ll, ll> inputB[SIZE / 2];
ll inline orientation(pair<ll, ll>& a, pair<ll, ll>& b, pair<ll, ll>& c) {
return (c.second - b.second) * (b.first - a.first) -
(b.second - a.second) * (c.first - b.first);
}
int binsearch(pair<ll, ll>& point, int h) {
int l = 0;
int result = -1;
while (l <= h) {
int mid = ((h - l) / 2) + l;
if (orientation(inputA[0], inputA[mid + 1], point) <= 0) {
result = mid;
if (l == h) {
break;
}
l = mid + 1;
}
else {
h = mid - 1;
}
}
return result;
}
int main()
{
//cin.tie(NULL);
int n, m;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> inputA[i].first >> inputA[i].second;
}
inputA[n] = inputA[0];
cin >> m;
for (int i = 0; i < m; i++) {
cin >> inputB[i].first >> inputB[i].second;
}
ll o1, o2, o3;
int triangleIndex;
pair<ll, ll> a = inputA[0], b, c, d;
bool flag = true;
for (int j = 0; j < m; j++) {
d = inputB[j];
triangleIndex = binsearch(d, n - 1);
if (triangleIndex < 0 || triangleIndex >= n - 1) {
flag = false;
break;
}
b = inputA[triangleIndex + 1];
c = inputA[triangleIndex + 2];
o1 = orientation(a, b, d);
o2 = orientation(b, c, d);
o3 = orientation(c, a, d);
if ((triangleIndex == 0 && (o1 >= 0 || o2 >= 0)) ||
(triangleIndex == n - 2 && (o2 >= 0 || o3 >= 0)) || (o2 >= 0)) {
flag = false;
break;
}
}
if (flag) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}
Given a set of points X, a convex hull is the smallest convex set that contains X.
Before going straight in the algorithm it is important to note that points on the extreme left, right, top and bottom will be the part of Convex Hull.
Take a point at extreme left-bottom
Swap this point with the first point.
Sort all the points except the first one.
Compare function calculates the orientation of two points
wrt first point. The first point is also called the pivot.
For points which are collinear sort them in non-increasing
order.
Make an empty output vector. Store the first two points in the
output vector.
Iterate through all the points calculating the orientation of
the current point with the last two points in the output.
Orientation < 0
Add the current point at the end of the output.
Orientation >= 0
While Orientation >=0 keep removing the last
point from the output(keep a check if the
number of points in the output > 2).
Add the current point at the end of the output.
There is a possibility that the last point 3 points selected, indirectly, by the above algorithm can be collinear. Using the above algorithm we are making sure that whenever any three points are collinear we remove the middle one. But to complete the convex hull the last point has to be connected to the starting point. Therefore the last two points and the first points can be all collinear. To avoid this situation what we can do it after sorting all the points we can append the starting point at the end. In this we will if the last two points and the starting point are collinear and remove the last one if necessary. The output will now contain the first point repeated. Once as the starting point and once as the end point. We will have to remove the this repeated point explicitly as shown in the code below.
#define SIZE 100001
using namespace std;
typedef long long ll;
pair<int, int> points[SIZE];
pair<int, int> output[SIZE];
pair<int, int> a;
long distance(pair<int, int>& a, pair<int, int>&b) {
return (b.first - a.first)* (b.first - a.first) +
(b.second - a.second)* (b.second - a.second);
}
long inline orientation(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c) {
// Positive: Clockwise
// Negative: Counter Clockwise
// Zero: Collinear Points
return ((long)b.second - (long)a.second) * ((long)c.first - (long)b.first) -
((long)c.second - (long)b.second) * ((long)b.first - (long)a.first);
}
bool inline orientation_1(pair<int, int>& b, pair<int, int>& c) {
long o = orientation(a, b, c);
if (o == 0) {
int d1 = distance(a, b);
int d2 = distance(a, c);
return d1 < d2;
}
return o < 0;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin.tie(NULL);
int n, u, v, m, lx = INT_MAX, ly, leftMostIndex;
long o;
cin >> n;
for (int j = 0; j < n; j++) {
cin >> u >> v;
points[j].first = u, points[j].second = v;
if (u < lx || (u == lx && v < ly)) {
lx = u, ly = v;
a = points[j];
leftMostIndex = j;
}
}
swap(points[0], points[leftMostIndex]);
sort(points + 1, points + n, orientation_1);
points[n] = points[0];
m = 2;
output[0] = points[0], output[1] = points[1];
for (int k = 2; k <= n; k++) {
o = orientation(output[m - 2], output[m - 1], points[k]);
if (o < 0) {
output[m++] = points[k];
}
else if (o >= 0) {
while (o >= 0) {
m--;
if (m < 2) {
break;
}
o = orientation(output[m - 2], output[m - 1], points[k]);
}
output[m++] = points[k];
}
}
for (int k = 0; k < m - 1; k++) {
cout << output[k].first << " " << output[k].second << endl;
}
return 0;
}