Connection Status:
Competition Arena > FamilyCrest

FamilyCrest

SRM 604 · 2013-12-22 · by cgy4ever

SRM 604 · 2013-12-22 · by cgy4ever · Geometry
Class Name: FamilyCrest
Return Type: String
Method Name: canBeInfinite
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel has a family crest. The crest is a simple line drawing that consists of several line segments. You are given the description of the crest as four equally long int[]s: A, B, C, and D. For each valid i, the crest contains a line segment that connects the points (A[i], B[i]) and (C[i], D[i]). Note that some of the given line segments may intersect and even overlap each other.

Fox Ciel got a large square piece of paper with side length 1,000,000,000. She is now going to draw some copies of her family crest onto the paper. All copies must have the same size as the original described by A, B, C, and D. Also, all copies must have the same orientation. In other words, once she draws the first copy, all other copies must be obtained by translation only (without any rotation or resizing). Additionally, the copies must be pairwise disjoint. (I.e., they are not allowed to share any points at all.)

Return "Infinite" (quotes for clarity) if it is possible to draw an infinite number of non-overlapping copies of the family crest onto the paper. Otherwise, return "Finite".

Constraints

  • A will contain between 1 and 50 elements, inclusive.
  • A, B, C and D will contain same number of elements.
  • Elements in A, B, C, D will be between -1,000 and 1,000, inclusive.
  • For each i, (A[i], B[i]) and (C[i], D[i]) will be different.
Examples
0)
{0}
{0}
{0}
{1}
Returns: "Infinite"

This family crest contains only one line segment: (0,0)-(0,1). We can easily draw an infinite number of disjoint copies of this family crest. For example, we can draw the segments (1/x,0) - (1/x,1) for each positive integer x. (Note that the vertices of the copies are not required to have integer coordinates.)

1)
{0,1,1,0}
{0,0,1,1}
{1,1,0,0}
{0,1,1,0}
Returns: "Finite"

This family crest is the unit square. It is clearly impossible for one unit square to contain another one, so each of them will have to be drawn outside of all others. And as the area of the whole paper is 1,000,000,000^2, we clearly cannot draw more than 1,000,000,000^2 copies of the unit square.

2)
{0,1,2,3}
{0,3,0,3}
{1,2,3,4}
{3,0,3,0}
Returns: "Infinite"
3)
{0,1,2,3,-1,-3,-1}
{0,3,0,3,3,2,1}
{1,2,3,4,-3,-1,-3}
{3,0,3,0,2,1,0}
Returns: "Finite"
4)
{0,2,4,6,-1,-2,-1}
{0,1,0,1,3,2,1}
{2,4,6,8,-2,-1,-2}
{1,0,1,0,2,1,0}
Returns: "Infinite"
7)
{-1,-2,0,1}
{0,0,0,0}
{1,0,2,-1}
{0,0,0,0}
Returns: "Infinite"

Note that the line segments that form the family crest may sometimes overlap.

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

Coding Area

Language: C++17 · define a public class FamilyCrest with a public method string canBeInfinite(vector<int> A, vector<int> B, vector<int> C, vector<int> D) · 107 test cases · 2 s / 256 MB per case

Submitting as anonymous