## Tuesday, August 9, 2016

[Solution]

[Time]
O(n) Average, O(n^2) worst case when there is no such triangle.
Or, sort first, then O(nlogn) time is guaranteed.

`public` `List<Point> findTriangle(List<Point> points) {`
`  ``List<Point> result = ``new` `ArrayList<>();`
`  ``if` `(points == ``null` `|| points.isEmpty()) {`
`    ``return` `result;`
`  ``}`
`  `
`  ``Point fstMin = ``null``;`
`  ``Point secMin = ``null``;`
`  `
`  ``for` `(Point point : points) {`
`    ``if` `(fstMin == ``null` `|| point.y < fstMin.y) {`
`      ``secMin = fstMin;`
`      ``fstMin = point;`
`    ``}`
`    ``else` `if` `(secMin == ``null` `|| point.y < secMin.y) {`
`      ``secMin = point;`
`    ``}`
`  ``}`
`  `
`  ``boolean``[] isVisited = ``new` `boolean``[points.size()];`
`  ``int` `cnt = ``2``;`
`  ``while` `(cnt < points.size()) {`
`    ``Point thirdMin = ``null``;`
`    ``int` `idx = -``1``;`
`    ``for` `(``int` `i = ``0``; i < points.size(); i++) {`
`      ``if` `(points[i].y >= secMin.y && points[i].y < thirdOne.y && !isVisited[i]) {        `
`        ``idx = i;`
`        ``thirdOne = point;`
`      ``}`
`    ``}`
`    `
`    ``if` `(!sameLine(fstMin, secMin, thirdMin)) {`
`      ``result.add(fstMin);`
`      ``result.add(secMin);`
`      ``result.add(thirdMin);`
`      ``break``;`
`    ``}`
`    ``else` `{`
`      ``isVisited[idx] = ``true``;`
`      ``cnt++;`
`    ``}`
`  ``}`
`  `
`  ``return` `result;`
`}`

`private` `boolean` `sameLine(Point a, Point b, Point c) {`
`  ``double` `k1 = (b.y - a.y) / (b.x - a.x);`
`  ``double` `k2 = (c.y - b.y) / (c.x - b.x);`
`  `
`  ``return` `k1 == k2;`
`}`