Connection Status:
Competition Arena > Polygon

Polygon

TCCC07 Wildcard · 2007-07-30 · by andrewzta

TCCC07 Wildcard · 2007-07-30 · by andrewzta · Geometry, Search
Class Name: Polygon
Return Type: String[]
Method Name: getKthPoint
Arg Types: (vector<int>, vector<int>, vector<string>)
Problem Statement

Problem Statement

You are given a polygon (possibly non-convex) with edges parallel to the coordinate axes. The polygon is non-self-intersecting, meaning that no two of its edges share any common points, with the exception of vertices, each of which is shared between exactly two adjacent edges.

Consider all points with integer coordinates inside the polygon (including the points on its border). Sort all of them lexicographically (first, by x-coordinate, then by y-coordinate). You will be asked to return the coordinates of some points in this list.

You are given int[]s x and y, the i-th elements of which are the x and y coordinates, respectively, of the i-th vertex of the polygon in a counterclockwise traversal. You are also given a String[] k, each element of which is the index of a point in the sorted list. Return a String[], the i-th element of which is the k[i]-th point with integer coordinates inside the polygon (1-based). Format each returned element as "x-coordinate y-coordinate" (quotes for clarity only, separate x and y coordinates with one space). For each i, if there are less than k[i] points, the corresponding element in the return value must be an empty String.

Constraints

  • x will contain between 4 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x will be between 0 and 10^9, inclusive.
  • Each element of y will be between 0 and 10^9, inclusive.
  • x and y will describe a counterclockwise traversal of vertices in a polygon.
  • The polygon described by x and y will have edges parallel to coordinate axes.
  • The polygon described by x and y will be non-self-intersecting.
  • All vertices of the polygon will be distinct.
  • k will contain between 1 and 50 elements, inclusive.
  • Each element of k will be an integer between 1 and 10^18, inclusive, with no leading zeroes.
Examples
0)
{0, 2, 2, 0}
{0, 0, 2, 2}
{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
Returns: {"0 0", "0 1", "0 2", "1 0", "1 1", "1 2", "2 0", "2 1", "2 2" }

These are all points that belong to a 2x2 square.

1)
{0,1,2,2,0}
{0,0,0,1,1}
{"1","6","2","3","5","4","7"}
Returns: {"0 0", "2 1", "0 1", "1 0", "2 0", "1 1", "" }

Note that there can be two consecutive parallel edges. Also note that k need not be sorted.

2)
{0, 5, 5, 3, 3, 4, 4, 3, 3, 0, 0, 1, 1, 0}
{0, 0, 1, 1, 2, 2, 5, 5, 4, 4, 3, 3, 1, 1}
{"1","4","6","7","12","15","20","25","28","29"}
Returns: {"0 0", "0 4", "1 1", "1 2", "2 2", "3 0", "3 5", "4 4", "5 1", "" }
3)
{0,0,1,1}
{1,0,0,1}
{"1","2","3","4"}
Returns: {"0 0", "0 1", "1 0", "1 1" }

Note that the first edge can be vertical.

4)
{245315124,245315124,245315360,245315360,249736789,249736789,252049441,252049441,254679173,254679173,245973669,245973669,245315360,245315360,245973669,245973669,245315124,245315124,244681513,244681513,239414437,239414437,239084906,239084906,239414437,239414437,242530941,242530941,243591322,243591322,244280214,244280214,244681513,244681513}
{373314982,369607903,369607903,366211062,366211062,368387568,368387568,369607903,369607903,373314982,373314982,373829243,373829243,375271677,375271677,375742839,375742839,379131933,379131933,379454862,379454862,379131933,379131933,373314982,373314982,373829243,373829243,375271677,375271677,375742839,375742839,375271677,375271677,373314982}
{"39295509386480","13340310826482","49211366253211","56875642260339","3977353374219","57162543055690","46080008639808","55309348666585","75508555518572","46796402187142","19381059239527","12114836636864","23031956430169","14073459678744","3343308777078","26821778138539","50534483395004","50687133271125","65663788405708","4533751512075","74214947307779","69064146626618","69104631763082","61487247973764","7317609401821","4336895801432","55701250008759","6582005755040","21823755210210","54392304588898","82726073555120","78082217981672","29759485172230","50538034256654","41685568169067","38180257727426","56297340383360","74964342449184","29379508360934","11710689949351","62305304689217","43718816261110","16465389363570","84041665619864","29361751413678","7105296917608","47472484093200","13424560661080","85010163350607","85010163350608"}
Returns: {"246278047 372335377", "241445047 377903751", "247673876 370256599", "248752756 367975247", "239780705 376093528", "248793142 369817092", "247233083 371292549", "248532273 368195336", "252116076 371109707", "247333928 369926638", "242518840 374940136", "241227209 377523693", "243387422 377174692", "241575370 379080753", "239667998 378249727", "244370979 376271802", "247860128 367904300", "247881616 368725973", "250101615 372322433", "239879609 377910904", "251837040 372048129", "250791705 370725993", "250799921 372220817", "249401919 371020549", "240374463 375241170", "239844617 373895301", "248587440 367527703", "240243703 377665589", "243098599 376284811", "248403183 369279539", "254063031 371204855", "252810332 371040327", "244963221 377630529", "247860628 366805450", "246614490 366624961", "246121056 372338034", "248671350 367891194", "251989127 371424429", "244897899 375757777", "241155369 375376980", "249517075 368609326", "246900704 373071910", "242000556 373900259", "254417917 372476719", "244894846 377964977", "240336722 379281377", "247429098 371671126", "241460023 378453229", "254679173 373314982", "" }

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

Coding Area

Language: C++17 · define a public class Polygon with a public method vector<string> getKthPoint(vector<int> x, vector<int> y, vector<string> k) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous