What programming language you start with really all depends on where you want to go with programming/coding. The great thing about this field is that there are an absolute abundance of smaller fields that you can go into, all using programming in their own unique ways. For web applications, a good start would be with HTML and later moving your way through CSS, JavaScript, JQuery, PHP, SQL, and any of the JavaScript libraries. Ruby is also a popular choice, so I would recommend checking that out too. For more scientific fields or areas with more machine learning and A.I., Python is generally a great place to start as it is widely used in that field of study. C++ is also a very useful language to know for that, but it can be a little more challenging for beginners. For game and application design, languages such as C#, C, Swift, Kotlin, and Java are most often used for that.
Description
You are given a number of points, forming the hull of a convex polygon. You are also given a number N.
Your goal is to partition the original polygon into N smaller polygons, all containing equal amount of space (surface, volume, ...), by adding at most one node, and as many edges as required.
If it is impossible to find a valid solution by adding the single node, you may give a result for the max number < N, for which a equitable partitioning is possible.
Input Description
First line is the number N, the second line contains coordinates of the nodes of the convex polygon. The third line contains the edges, where the numbers represent the index of the nodes.
For example:
2
(0 0)(0.5 0.5)(0 1)
(1 2)(2 3)(3 1)
Output Description
You should return all added nodes.
Optional: Display your result by plotting the nodes and edges.
For example:
(0 0.5)
Challenge inputs
3
(0.49 0.7)(0.23 0.64) (0.95 0.48)
(1 2)(2 3)(3 1)
4
(0.49 0.7)(1.23 0.64) (0.95 1.48)
(1 2)(2 3)(3 1)
2
(1.49 0.7)(0.23 0.64) (0.95 1.48)
(1 2)(2 3)(3 1)
5
(1 0)(0 1)(2 1)(0 2)(1 3)
(1 2)(2 3)(3 4)(4 5)(5 1)
Bonus Challenge Inputs
2
(0)(1)
(1 2)
4
(1 2 3)(3 2 1)(2 1 3)
(1 2)(2 3)(3 1)
3
(0 0 1)(0 1 0)(0 0 1)(1 1 1)
(1 2)(1 3)(1 4)(2 3)(2 4)(3 4)
3
(0 0 1 39789)(0 1 0 39872)(0 0 1 41234)(1 1 1 42546)
(1 2)(1 3)(1 4)(2 3)(2 4)(3 4)
Solution
in pseudo
no bonus
add point, connect to H hull nodes, creating regions
define volume of region
define cost as difference between volumes and total volume / N
if H < N, for H-N, cost is volume
use multi variate gradient descent to minimize cost
if total cost = 0 at minimum, return point
else try N-1
bonus
generalise space_volume (using matrix determinants?)
bonus++
linear programming?
You are given a number of points, forming the hull of a convex polygon. You are also given a number N.
Your goal is to partition the original polygon into N smaller polygons, all containing equal amount of space (surface, volume, ...), by adding at most one node, and as many edges as required.
If it is impossible to find a valid solution by adding the single node, you may give a result for the max number < N, for which a equitable partitioning is possible.
Input Description
First line is the number N, the second line contains coordinates of the nodes of the convex polygon. The third line contains the edges, where the numbers represent the index of the nodes.
For example:
2
(0 0)(0.5 0.5)(0 1)
(1 2)(2 3)(3 1)
Output Description
You should return all added nodes.
Optional: Display your result by plotting the nodes and edges.
For example:
(0 0.5)
Challenge inputs
3
(0.49 0.7)(0.23 0.64) (0.95 0.48)
(1 2)(2 3)(3 1)
4
(0.49 0.7)(1.23 0.64) (0.95 1.48)
(1 2)(2 3)(3 1)
2
(1.49 0.7)(0.23 0.64) (0.95 1.48)
(1 2)(2 3)(3 1)
5
(1 0)(0 1)(2 1)(0 2)(1 3)
(1 2)(2 3)(3 4)(4 5)(5 1)
Bonus Challenge Inputs
2
(0)(1)
(1 2)
4
(1 2 3)(3 2 1)(2 1 3)
(1 2)(2 3)(3 1)
3
(0 0 1)(0 1 0)(0 0 1)(1 1 1)
(1 2)(1 3)(1 4)(2 3)(2 4)(3 4)
3
(0 0 1 39789)(0 1 0 39872)(0 0 1 41234)(1 1 1 42546)
(1 2)(1 3)(1 4)(2 3)(2 4)(3 4)
Solution
in pseudo
no bonus
add point, connect to H hull nodes, creating regions
define volume of region
define cost as difference between volumes and total volume / N
if H < N, for H-N, cost is volume
use multi variate gradient descent to minimize cost
if total cost = 0 at minimum, return point
else try N-1
bonus
generalise space_volume (using matrix determinants?)
bonus++
linear programming?
Comments
Post a Comment