6
0
Input: An integer N which represents the polygon's vertices and a list of their x and y coordinates.
Expected output: The smallest difference possible between the area of the(not necessarily convex) polygon and the triangle containing it. The triangle also has to share at least 2 vertices with the polygon. If there is no such triangle print -1.
Example:
4
0,0
2,0
1,1
0,2
Output: 0, because the polygon matches up perfectly with the triangle.
This is code-golf so answers will be scored in bytes with less bytes being better.
McLinux
Posted 2017-12-23T21:53:33.717
Reputation: 295
1Welcome to PPCG! As it stands, your question is a little unclear. Could you provide some example inputs and outputs? – Conor O'Brien – 2017-12-23T21:56:02.880
Of course, sorry! – McLinux – 2017-12-23T22:00:29.280
Also, most challenges on this site tend to be asking for answers to be shortest in length. If this is the case, please add the [tag:code-golf] tag to your post. – Conor O'Brien – 2017-12-23T22:02:42.050
2
If there is no such triangle print -1the standard on this site is to ignore invalid inputs, letting them lead to undefined beviour or erroring out. – Uriel – 2017-12-23T22:21:33.380apart from that, although it lacks a bit of sources to help people who are not familiar with these subjects (not mandatory), this is a good challenge. – Uriel – 2017-12-23T22:22:49.253
1@Uriel Ignoring invalid input isn't a standard iirc, it's just sometimes a recommendation. It is by no means mandatory. – Conor O'Brien – 2017-12-23T22:52:21.670
How does any triangle match up perfectly with ((0,0),(2,0),(2,1),(0,2))? EDIT: should the (2,1) be (1,1)? (I believe the answer for using the (2,1) would be 1) – Jonathan Allan – 2017-12-23T23:23:52.633
Yes, it is 1,1. Sorry about the mistake. – McLinux – 2017-12-23T23:30:08.337
2It isn’t quite clear which way “The triangle also…” is supposed to modify the previous sentence. Do you mean “find the smallest triangle among all triangles that both contain the polygon and share at least 2 vertices with it”? Or do you mean “find the smallest triangle among all triangles that contain the polygon; then, if that triangle doesn’t share 2 vertices with it, print −1”? Please edit the question to clarify this. – Anders Kaseorg – 2017-12-24T02:36:30.267
The first of your questions. “find the smallest triangle among all triangles that both contain the polygon and share at least 2 vertices with it” – McLinux – 2017-12-24T12:03:18.067
Another case of “Should’ve been sandboxed”, otherwise nice question – Stan Strum – 2017-12-25T01:03:20.907
You mention that the polygon is not necessarily convex. Is it possible that it won't be concave either (i.e. that it will be complex)? – Tutleman – 2017-12-29T00:09:58.217
@Uriel <s>There must be such a triangle. Also </s> are the terms complex enough for more explanation? "A triangle is a polygon with 3 sides"? Doesn't seem good to me. – user202729 – 2017-12-31T02:13:40.287