Connection Status:
Competition Arena > CheckPolygon

CheckPolygon

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary · Geometry
Class Name: CheckPolygon
Return Type: String
Method Name: check
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

A simple polygon is a polygon with the following properties:

  • the length of each side is positive
  • no two consecutive sides are parallel
  • no two non-consecutive sides share a common point

You are given two int[]s X and Y, each with N elements. Find out whether there is a simple polygon whose vertices (in the order in which they lie on its boundary) are the points (X[0], Y[0]), (X[1], Y[1]), ... (X[N-1], Y[N-1]).

If the given points are the vertices of a simple polygon, calculate its area A and return a String that contains the decimal representation of A with one digit after the decimal point. If the given points are not the vertices of a simple polygon, return the String "Not simple" (quotes for clarity).

Notes

  • The correct return value is always uniquely defined by problem statement. In particular, if the points represent a valid polygon, its area is always a rational number with at most one decimal digit.

Constraints

  • X will contain between 3 and 50 elements, inclusive.
  • Each element of X will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • X and Y will contain same number of elements.
  • Each element of Y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
{0,0,1}
{0,1,0}
Returns: "0.5"

These three points are the vertices of a small triangle.

1)
{0,1,2,0,2}
{0,2,0,1,1}
Returns: "Not simple"

These points, in the given order, are not the vertices of a simple polygon. The closed polyline that passes through these five points intersets itself five times.

2)
{0,1,2,1,0,1}
{0,0,1,2,2,1}
Returns: "2.0"

Note that you must return the string "2.0". The printed number must have exactly one decimal place, even if that digit is zero. The string "2" is not a correct answer.

3)
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}
{1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}
Returns: "Not simple"
4)
{0,1,1}
{-1000000000,1000000000,999999999}
Returns: "0.5"

Submissions are judged against all 33 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CheckPolygon with a public method string check(vector<int> X, vector<int> Y) · 33 test cases · 2 s / 256 MB per case

Submitting as anonymous