Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 42 lines (36 sloc) 1.217 kb
4476c34 Selection sort and radix sort
Andrey Paramonov authored
1 /*
2 * Three distinct points are plotted at random on a Cartesian plane,
3 * for which -1000 <= x, y <= 1000, such that a triangle is formed.
4 *
5 * Consider the following two triangles:
6 *
7 * A(-340,495), B(-153,-910), C(835,-947)
8 * X(-175,41), Y(-421,-714), Z(574,-645)
9 *
10 * It can be verified that triangle ABC contains the origin, whereas
11 * triangle XYZ does not.
12 *
13 * Using triangles.txt, a 27K text file containing the co-ordinates
14 * of one thousand "random" triangles, find the number of triangles
15 * for which the interior contains the origin.
16 */
17
18 boolean insideTriangle(t, x) {
19 insideTriangle(t[0,1], t[2,3], t[4,5], x)
20 }
21
22 boolean insideTriangle(a, b, c, x) {
23 onSemiPlane(a, b, c, x) && onSemiPlane(b, c, a, x) && onSemiPlane(c, a, b, x)
24 }
25
26 boolean onSemiPlane(a, b, c, d) {
27 onLine(a, b, c) * onLine(a, b, d) >= 0
28 }
29
30 long onLine(a, b, c) {
31 (c[0] - a[0]) * (b[1] - a[1]) - (c[1] - a[1]) * (b[0] - a[0])
32 }
33
34 assert insideTriangle([-340,495],[-153,-910],[835,-947],[0,0])
35 assert !insideTriangle([-175,41,-421,-714,574,-645],[0,0])
36
37 int count = 0
38 new File('triangles.txt').eachLine {
39 def triangle = it.split(/,/)*.toInteger()
40 if (insideTriangle(triangle, [0,0])) count++
41 }
42 println count
Something went wrong with that request. Please try again.