Monday, December 22, 2014

SRM 641 div 2 500

this is my source ..

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;
  }
 }
 
}

No comments:

Post a Comment