Connection Status:
Competition Arena > PointInPolygon

PointInPolygon

SRM 187 · 2004-03-16 · by Rustyoldman

SRM 187 · 2004-03-16 · by Rustyoldman · Geometry
Class Name: PointInPolygon
Return Type: String
Method Name: testPoint
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

Given a test point, (testPointX, testPointY), and the vertices of a simple polygon, vertices, determine if the test point is in the interior, in the exterior or on the boundary of the polygon. Return the String "INTERIOR", "EXTERIOR", or "BOUNDARY".

For simplicity, all sides of the polygon will be horizontal or vertical, and the vertices and the test point will all be at integer coordinates. The x and y coordinates of the vertices will given in the String[] vertices where each element represents a single vertex, formatted as "<x> <y>". There is an edge from vertices[i] to vertices[i+1] for i from 0 to n-2, and an edge from vertices[n-1] to vertices[0] where n is the number of vertices (and the number of edges) in the polygon.

Notes

  • A simple polygon is a polygon that may or may not be convex, but self-intersection is not allowed. Not even at a single point.

Constraints

  • vertices will contain an even number of elements between 4 and 50 inclusive.
  • Each element of vertices is formatted as follows " " (quotes for clarity). With exactly one space between and and no leading or trailing spaces.
  • and will consist of an optional minus sign followed by between 1 and 4 digit characters inclusive. There will be no leading zeros.
  • Each and value in each element of vertices will be between -1000 and 1000 inclusive.
  • The elements of vertices taken in order will specify the vertices of a valid simple polygon.
  • Each edge of this polygon will be either exactly horizontal or exactly vertical.
  • No three consecutive vertices will be colinear.
  • No two elements of vertices will be the same.
  • No edges will overlap or intersect, except where adjacent edges meet pairwise at vertices.
  • testPointX and testPointY will both be between -1000 and 1000 inclusive
Examples
0)
{"0 0",
 "0 10",
 "10 10",
 "10 0"}
5
5
Returns: "INTERIOR"

A simple example of a square of side 10.

1)
{"0 0",
 "0 10",
 "10 10",
 "10 0"}
10
15
Returns: "EXTERIOR"

Outside the same square.

2)
{"0 0",
 "0 10",
 "10 10",
 "10 0"}
5
10
Returns: "BOUNDARY"

On an edge of the square

3)
{"-100 -90", "-100 100","100 100", "100 -100",
 "-120 -100","-120 100","-130 100","-130 -110",
 "110 -110", "110 110", "-110 110","-110 -90"}
0
0
Returns: "EXTERIOR"

A more complex geometry

4)
{"0 0","0 1000","1000 1000","1000 800",
 "200 800","200 600","600 600","600 400",
 "200 400","200 200","1000 200","1000 0"}
100
500
Returns: "INTERIOR"

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

Coding Area

Language: C++17 · define a public class PointInPolygon with a public method string testPoint(vector<string> vertices, int testPointX, int testPointY) · 39 test cases · 2 s / 256 MB per case

Submitting as anonymous