### SRM 641 div 2 500

this is my source ..

point in triangle is somehow difficult to understand

find the algorithm

and when calling pointInTriangle

point.set method called many times.

so later, I have to do refactoring my code to speed up

point in triangle is somehow difficult to understand

find the algorithm

**point in triangle**and when calling pointInTriangle

point.set method called many times.

so later, I have to do refactoring my code to speed up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | package srm641; public class TrianglesContainOriginEasy { public int count(int[] x, int[] y){ int len = x.length; int count = 0; Point v1 = new Point(); Point v2 = new Point(); Point v3 = new Point(); for(int i=0; i<len; i++){ for(int j=i+1; j<len; j++){ for(int k=j+1; k<len; k++){ if(pointInTriangle(new Point(0, 0), v1.set(x[i], y[i]), v2.set(x[j], y[j]), v3.set(x[k], y[k]))){ count++; } } } } return count; } boolean pointInTriangle(Point pt, Point v1, Point v2, Point v3){ Boolean b1, b2, b3; b1 = sign(pt, v1, v2) < 0; b2 = sign(pt, v2, v3) < 0; b3 = sign(pt, v3, v1) < 0; return ((b1 == b2) && (b2== b3)); } private int sign(Point p1, Point p2, Point p3) { return (p1.x- p3.x) * (p2.y-p3.y) - (p2.x-p3.x)*(p1.y-p3.y); } class Point { int x, y; Point(int x, int y){ this.x = x; this.y = y; } Point(){ } public Point set(int x, int y){ this.x = x; this.y = y; return this; } } } |

## Comments

## Post a Comment