Check whether a given polygon in a 2D plane is convex; if not, return the index of a vertex that doesn't belong to the convex hull.
Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
AVAILABLE EXERCISES:
Exercise 9
Bitwise operations (bit-ops)
Exercise 8
Frontend
Exercise 7
Data Structures
Exercise 6
SQL
Exercise 5
Coding skills
Exercise 4
Algorithmic skills
Exercise 3
2017 Contest
Exercise 2
2016 Contest
Exercise 1
2015 Contest
Spoken language:
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
struct Point2D { int x; int y; };
Write a function:
int solution(struct Point2D A[], int N);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
struct Point2D { int x; int y; };
Write a function:
int solution(vector<Point2D> &A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
struct Point2D { int x; int y; };
Write a function:
int solution(vector<Point2D> &A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { public int x; public int y; };
Write a function:
class Solution { public int solution(Point2D[] A); }
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { int x = 0; int y = 0; }
Write a function:
int solution(List<Point2D> A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
type Point2D struct { X int Y int }
Write a function:
func Solution(A []Point2D) int
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].X to access the x-coordinate,
- A[K].Y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { public int x; public int y; }
Write a function:
class Solution { public int solution(Point2D[] A); }
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { public int x; public int y; }
Write a function:
class Solution { public int solution(Point2D[] A); }
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
// Point2D obj is an Object with attributes // obj.x - type: int // obj.y - type: int
Write a function:
function solution(A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
-- Point2D obj is an object with attributes -- obj.x - type: int -- obj.y - type: int
Write a function:
function solution(A)
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Note: All arrays in this task are zero-indexed, unlike the common Lua convention. You can use #A to get the length of the array A.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
@interface Point2D : NSObject { @public int x; int y; } @end @implementation Point2D @end
Write a function:
int solution(NSMutableArray *A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- ((Point2D *)[A objectAtIndex: K])->x to access the x-coordinate,
- ((Point2D *)[A objectAtIndex: K])->y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
Point2D = record x : longint; y : longint; end;
Write a function:
function solution(A: array of Point2D; N: longint): longint;
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { var $x = 0; var $y = 0; }
Write a function:
function solution($A);
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- $A[$K]->x to access the x-coordinate,
- $A[$K]->y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
# Point2D is a dictionary with keys # 'x' - type: int # 'y' - type: int
Write a function:
sub solution { my (@A) = @_; ... }
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- $A[$K]->{x} to access the x-coordinate,
- $A[$K]->{y} to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
from dataclasses import dataclass, field @dataclass class Point2D: x: int y: int
Write a function:
def solution(A)
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D attr_accessor :x, :y end
Write a function:
def solution(a)
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D(var x: Int, var y: Int)
Write a function:
object Solution { def solution(a: Array[Point2D]): Int }
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A(K).x to access the x-coordinate,
- A(K).y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
public struct Point2D { public var x: Int = 0; public var y: Int = 0; public init() {}; }
Write a function:
public func solution(_ A : inout [Point2D]) -> Int
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
class Point2D { x: number; y: number; constructor(x: number = 0, y: number = 0) { this.x = x; this.y = y; } }
Write a function:
function solution(A: Point2D[]): number;
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A[K].x to access the x-coordinate,
- A[K].y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
An array A of points in a 2D plane is given. These points represent a polygon: every two consecutive points describe an edge of the polygon, and there is an edge connecting the last point and the first point in the array.
A set of points in a 2D plane, whose boundary is a straight line, is called a semiplane. More precisely, any set of the form {(x, y) : ax + by ≥ c} is a semiplane. The semiplane contains its boundary.
A polygon is convex if and only if, no line segment between two points on the boundary ever goes outside the polygon.
For example, the polygon consisting of vertices whose Cartesian coordinates are consecutively:
(-1, 3) (3, 1) (0, -1) (-2, 1)is convex.
The convex hull of a finite set of points in a 2D plane is the smallest convex polygon that contains all points in this set. For example, the convex hull of a set consisting of seven points whose Cartesian coordinates are:
(-1, 3) (1, 2) (3, 1) (1, 1) (0, -1) (-2, 1) (-1, 2)is a polygon that has five vertices. When traversed clockwise, its vertices are:
(-1, 3) (1, 2) (3, 1) (0, -1) (-2, 1)
If a polygon is concave (that is, it is not convex), it has a vertex which does not lie on its convex hull border. Your assignment is to find such a vertex.
Assume that the following declarations are given:
Class Point2D Public x As Integer Public y As Integer End Class
Write a function:
Private Function solution(A As Point2D()) As Integer
that, given a non-empty array A consisting of N elements describing a polygon, returns −1 if the polygon is convex. Otherwise, the function should return the index of any point that doesn't belong to the convex hull border. Note that consecutive edges of the polygon may be collinear (that is, the polygon might have 180−degrees angles).
To access the coordinates of the K-th point (where 0 ≤ K < N), use the following syntax:
- A(K).x to access the x-coordinate,
- A(K).y to access the y-coordinate.
For example, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 3 A[2].y = 1 A[3].x = 0 A[3].y = -1 A[4].x = -2 A[4].y = 1the function should return −1, as explained in the example above.
However, given array A such that:
A[0].x = -1 A[0].y = 3 A[1].x = 1 A[1].y = 2 A[2].x = 1 A[2].y = 1 A[3].x = 3 A[3].y = 1 A[4].x = 0 A[4].y = -1 A[5].x = -2 A[5].y = 1 A[6].x = -1 A[6].y = 2the function should return either 2 or 6. These are the indices of the polygon lying strictly in its convex hull (that is, not on the convex hull border).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [3..10,000];
- the coordinates of each point in array A are integers within the range [−1,000,000,000..1,000,000,000];
- no two edges of the polygon A intersect, other than meeting at their endpoints;
- array A does not contain duplicate points.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
