Statistics

PROBLEM STATEMENT

A certain screensaver draws line segments on a two-dimensional screen.  Given
the coordinates of the line segments drawn, determine the number of distinct
intersection points.

If any two of the line segments intersect at more than one point (i.e. their
intersection is a line segment), then you should return -1.

DEFINITION

Class: ScreenSaver
Method name: crossings
Parameters: String[]
Returns: int

Here is the method signature (be sure your method is public): int
crossings(String[] segments);

NOTE

Each segment is of the form "<x1> <y1> <x2> <y2>"  (quotes are not in the
segment and are included for clarity).

x1,y1,x2,y2 are non-negative integers separated by single spaces.

(x1,y1) and (x2,y2) are the coordinates of the two endpoints of the segment.

If three or more line segments intersect at the same point, that point should
only be counted once (See example 4).

If any two of the line segments intersect each other at more than one point,
return -1 (See example 3).

Line segments may intersect at their endpoints (See example 5).

Topcoder will ensure that:

* The number of segments is between 1 and 50, inclusive
* Every segment is of the form "<x1> <y1> <x2> <y2>" such that 0 <= x1,y1,x2,y2
<= 1000
* For every segment, (x1,y1) is not the same point as (x2,y2)
  i.e. degenerate line segments such as "4 5 4 5" are not allowed

EXAMPLES

1.  segments = {"0 0 2 2", "0 2 2 0"}
    Method returns 1

2.  segments = {"0 0 2 2", "0 1 2 6"}
    Method returns 0

3.  segments = {"0 0 2 2", "1 1 3 3", "9 8 7 6"}
    Method returns -1  (the first two segments intersect at more than one point)

4.  segments = {"0 0 2 2", "0 2 2 0", "0 1 10 1", "1 0 1 1000"}
    Method returns 1  (only one distinct intersection point)

5.  segments = {"0 0 17 1", "17 1 1 17", "1 17 0 0"}
    Method returns 3

6.  segments = {"0 0 3 3", "1 0 2 3", "2 0 1 3", "3 0 0 3",  "3 1 0 2", "3 2 0
1"}
    Method returns 1

7.  segments = {"999 999 1000 1000", "1000 1000 999 999"}
    Method returns -1