khalfella

Untitled

Nov 30th, 2016
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.91 KB | None | 0 0
  1. % Enter your code here. Read input from STDIN. Print output to STDOUT
  2. % Your class should be named solution
  3.  
  4. -module(solution).
  5. -export([main/0]).
  6.  
  7. points_left_to_line({Ax, Ay}, {Bx, By}, Points) ->
  8. lists:foldl(fun({Px, Py}, Acc) ->
  9. case (((Bx - Ax) * (Py - Ay)) - ((By - Ay) * (Px - Ax))) > 0 of
  10. true -> [{Px, Py}|Acc];
  11. false -> Acc
  12. end
  13. end, [], Points).
  14.  
  15.  
  16. distance_from_line({Ax, Ay}, {Bx, By}, {Px, Py}) ->
  17. ABx = Bx - Ax,
  18. ABy = By - Ay,
  19. abs(ABx *(Ay - Py) - ABy * (Ax - Px)).
  20.  
  21.  
  22. distant_point(A, B, Points) ->
  23. lists:foldl(fun(P={Px,Py}, F={Fx, Fy}) ->
  24. DF = distance_from_line(A, B, F),
  25. DP = distance_from_line(A, B, P),
  26. case (DP > DF) or ((DP =:= DF) and (Px < Fx)) or ((DP =:= DF) and (Px =:= Fx) and (Py < Fy)) of
  27. true -> P;
  28. false -> F
  29. end
  30. end, lists:nth(1, Points), Points).
  31.  
  32.  
  33. hull_set(_A, _B, [], Hull) -> Hull;
  34. hull_set(_A, _B, [P], Hull) -> [P|Hull];
  35. hull_set(A, B, Points, Hull) ->
  36. F = distant_point(A, B, Points),
  37. OPoints = lists:delete(F, Points),
  38. LPoints = points_left_to_line(A, F, OPoints),
  39. RPoints = points_left_to_line(F, B, OPoints),
  40. LHull = hull_set(A, F, LPoints, [F|Hull]),
  41. hull_set(F, B, RPoints, LHull).
  42.  
  43.  
  44. left_right_points(Points) ->
  45. lists:foldl( fun({Px, Py}, []) -> [{Px, Py}, {Px, Py}];
  46. ({Px, Py}, [{Lx,Ly}, {Rx,Ry}]) ->
  47. L1 = case (Px < Lx) or ((Px =:= Lx) and (Py < Ly)) of
  48. true -> {Px, Py};
  49. false -> {Lx, Ly}
  50. end,
  51. R1 = case (Px > Rx) or ((Px =:= Rx) and (Py > Ry))of
  52. true -> {Px, Py};
  53. false -> {Rx, Ry}
  54. end,
  55. [L1, R1]
  56. end, [], Points).
  57.  
  58. all_points_left_to_line({Ax, Ay}, {Bx, By}, Points) ->
  59. lists:foldl(fun(_ , false) -> false;
  60. ({Px, Py}, true) -> (((Bx - Ax) * (Py - Ay)) - ((By - Ay) * (Px - Ax))) > 0
  61. end, true, Points).
  62.  
  63.  
  64. list_of_lines_in_hull(Hull) ->
  65. SHull = lists:zip(lists:seq(1, length(Hull)), Hull),
  66. LLines = [{{Ax, Ay}, {Bx, By}} || {An,{Ax, Ay}} <- SHull, {Bn, {Bx, By}} <- SHull, An =/= Bn],
  67. lists:foldl(fun({{Ax, Ay}, {Bx, By}}, Acc) ->
  68. RemHull = lists:delete({Bx, By},lists:delete({Ax, Ay}, Hull)),
  69. case all_points_left_to_line({Ax, Ay}, {Bx, By}, RemHull) of
  70. true -> [{{Ax, Ay}, {Bx, By}}| Acc];
  71. false -> Acc
  72. end
  73. end, [], LLines).
  74.  
  75. line_length({{Ax, Ay}, {Bx, By}}) ->
  76. math:sqrt(math:pow(Bx - Ax,2) + math:pow(By - Ay, 2)).
  77.  
  78. calculate_perimeter(Lines) ->
  79. lists:foldl(fun(Line, Acc) -> line_length(Line) + Acc end, 0, Lines).
  80.  
  81. quick_hull([A]) -> [A];
  82. quick_hull([A, B]) -> [A, B];
  83. quick_hull(Points) ->
  84. [A, B] = left_right_points(Points),
  85. RemPoints = lists:delete(B, lists:delete(A, Points)),
  86. LPoints = points_left_to_line(A, B, RemPoints),
  87. RPoints = points_left_to_line(B, A, RemPoints),
  88. LHull = hull_set(A, B, LPoints, [A,B]),
  89. Hull = hull_set(B, A, RPoints, LHull),
  90. LHLines = list_of_lines_in_hull(Hull),
  91. % io:format("Hull = ~w (~p) LHLines ~w (~p)~n", [Hull, length(Hull), LHLines, length(LHLines)]),
  92. calculate_perimeter(LHLines).
  93.  
  94.  
  95.  
  96. read_input(0, Acc) -> Acc;
  97. read_input(N, Acc) ->
  98. {ok,[X, Y]} = io:fread("", "~d ~d"),
  99. read_input(N - 1, [{X,Y}|Acc]).
  100.  
  101. main() ->
  102. {ok, [N]} = io:fread("", "~d"),
  103. Points = read_input(N, []),
  104. Hull = quick_hull(Points),
  105. io:format("~p~n",[Hull]).
Advertisement
Add Comment
Please, Sign In to add comment