Connection Status:
Competition Arena > Ear

Ear

SRM 558 · 2012-06-05 · by ir5

SRM 558 · 2012-06-05 · by ir5 · Brute Force, Geometry
Class Name: Ear
Return Type: long
Method Name: getCount
Arg Types: (vector<string>, vector<string>, vector<string>)
Problem Statement

Problem Statement

There are some red points and blue points on the Cartesian plane. All red points are on the x-axis and all blue points are in the upper half-plane. That is, the y-coordinate of each red point is 0, and the y-coordinate of each blue point is strictly positive.

Fox Ciel wants to form an ear-shaped figure using these points. She defines that the pair of four different red points A, B, C, D and two blue points P, Q is called an ear if and only if all the following conditions are satisfied.

  • Both points B and C lie strictly inside the segment AD.
  • The angles PAD, PDA, QBC and QCB are strictly less than 90 degrees.
  • Point Q is strictly inside of the triangle PAD.
In the following image, points in the left figure form an ear while points in the right figure do not.

You are given three String[]s redX, blueX and blueY. Concatenate all elements of redX to get a space-separate list of integers. The i-th integer of this list represents the x-coordinate of i-th red point. In the same way, blueX and blueY encode lists of x-coordinates and y-coordinates of blue points.

Your method must return the number of ways in which we can choose the four red and two blue points that form an ear.

Notes

  • The order of points in an ear does not matter. I.e., if two ears have the same four red and two blue points, they are considered the same.

Constraints

  • redX, blueX and blueY will each contain between 1 and 50 elements, inclusive.
  • Each element of redX, blueX and blueY will contain between 1 and 50 characters, inclusive.
  • After concatenating the elements of redX, the resulting string will be a single space separated list of integers.
  • After concatenating the elements of blueX, the resulting string will be a single space separated list of integers.
  • After concatenating the elements of blueY, the resulting string will be a single space separated list of integers.
  • There will be between 1 and 300 integers in each of the lists.
  • The number of integers in the lists of blueX and blueY will be the same.
  • Each integer in the lists will be between 1 and 10,000, inclusive.
  • All the integers in each list will be distinct.
  • Integers in the lists will have no leading zeros.
Examples
0)
{"3 2 8 7"}
{"5 4"}
{"2 4"}
Returns: 1

This case corresponds to the left figure in the statement.

1)
{"3 2 8 7"}
{"2 8"}
{"3 4"}
Returns: 0

This case corresponds to the right figure in the statement.

2)
{"1 2 6 9"}
{"3 6 8 5"}
{"1 5 4 3"}
Returns: 4

There exists only one possible combinations of A, B, C and D since there are only four red points. Possible combinations of P and Q are as follows. {(5, 3), (3, 1)} {(6, 5), (3, 1)} {(8, 4), (3, 1)} {(6, 5), (5, 3)}

3)
{"10000"}
{"10000 9999"}
{"10000 9999"}
Returns: 0

It is impossible to choose four red points from only one red point.

4)
{"100 2", "00", " 39", "9", " 800 900 9", "99"}
{"15", "0 250 ", "349"}
{"2 3 1"}
Returns: 12

Concatenate each element of the String[]s correctly.

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

Coding Area

Language: C++17 · define a public class Ear with a public method long long getCount(vector<string> redX, vector<string> blueX, vector<string> blueY) · 68 test cases · 2 s / 256 MB per case

Submitting as anonymous