Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- % Enter your code here. Read input from STDIN. Print output to STDOUT
- % Your class should be named solution
- -module(solution).
- -export([main/0]).
- points_left_to_line({Ax, Ay}, {Bx, By}, Points) ->
- lists:foldl(fun({Px, Py}, Acc) ->
- case (((Bx - Ax) * (Py - Ay)) - ((By - Ay) * (Px - Ax))) > 0 of
- true -> [{Px, Py}|Acc];
- false -> Acc
- end
- end, [], Points).
- distance_from_line({Ax, Ay}, {Bx, By}, {Px, Py}) ->
- ABx = Bx - Ax,
- ABy = By - Ay,
- abs(ABx *(Ay - Py) - ABy * (Ax - Px)).
- distant_point(A, B, Points) ->
- lists:foldl(fun(P={Px,Py}, F={Fx, Fy}) ->
- DF = distance_from_line(A, B, F),
- DP = distance_from_line(A, B, P),
- case (DP > DF) or ((DP =:= DF) and (Px < Fx)) or ((DP =:= DF) and (Px =:= Fx) and (Py < Fy)) of
- true -> P;
- false -> F
- end
- end, lists:nth(1, Points), Points).
- hull_set(_A, _B, [], Hull) -> Hull;
- hull_set(_A, _B, [P], Hull) -> [P|Hull];
- hull_set(A, B, Points, Hull) ->
- F = distant_point(A, B, Points),
- OPoints = lists:delete(F, Points),
- LPoints = points_left_to_line(A, F, OPoints),
- RPoints = points_left_to_line(F, B, OPoints),
- LHull = hull_set(A, F, LPoints, [F|Hull]),
- hull_set(F, B, RPoints, LHull).
- left_right_points(Points) ->
- lists:foldl( fun({Px, Py}, []) -> [{Px, Py}, {Px, Py}];
- ({Px, Py}, [{Lx,Ly}, {Rx,Ry}]) ->
- L1 = case (Px < Lx) or ((Px =:= Lx) and (Py < Ly)) of
- true -> {Px, Py};
- false -> {Lx, Ly}
- end,
- R1 = case (Px > Rx) or ((Px =:= Rx) and (Py > Ry))of
- true -> {Px, Py};
- false -> {Rx, Ry}
- end,
- [L1, R1]
- end, [], Points).
- all_points_left_to_line({Ax, Ay}, {Bx, By}, Points) ->
- lists:foldl(fun(_ , false) -> false;
- ({Px, Py}, true) -> (((Bx - Ax) * (Py - Ay)) - ((By - Ay) * (Px - Ax))) > 0
- end, true, Points).
- list_of_lines_in_hull(Hull) ->
- SHull = lists:zip(lists:seq(1, length(Hull)), Hull),
- LLines = [{{Ax, Ay}, {Bx, By}} || {An,{Ax, Ay}} <- SHull, {Bn, {Bx, By}} <- SHull, An =/= Bn],
- lists:foldl(fun({{Ax, Ay}, {Bx, By}}, Acc) ->
- RemHull = lists:delete({Bx, By},lists:delete({Ax, Ay}, Hull)),
- case all_points_left_to_line({Ax, Ay}, {Bx, By}, RemHull) of
- true -> [{{Ax, Ay}, {Bx, By}}| Acc];
- false -> Acc
- end
- end, [], LLines).
- line_length({{Ax, Ay}, {Bx, By}}) ->
- math:sqrt(math:pow(Bx - Ax,2) + math:pow(By - Ay, 2)).
- calculate_perimeter(Lines) ->
- lists:foldl(fun(Line, Acc) -> line_length(Line) + Acc end, 0, Lines).
- quick_hull([A]) -> [A];
- quick_hull([A, B]) -> [A, B];
- quick_hull(Points) ->
- [A, B] = left_right_points(Points),
- RemPoints = lists:delete(B, lists:delete(A, Points)),
- LPoints = points_left_to_line(A, B, RemPoints),
- RPoints = points_left_to_line(B, A, RemPoints),
- LHull = hull_set(A, B, LPoints, [A,B]),
- Hull = hull_set(B, A, RPoints, LHull),
- LHLines = list_of_lines_in_hull(Hull),
- % io:format("Hull = ~w (~p) LHLines ~w (~p)~n", [Hull, length(Hull), LHLines, length(LHLines)]),
- calculate_perimeter(LHLines).
- read_input(0, Acc) -> Acc;
- read_input(N, Acc) ->
- {ok,[X, Y]} = io:fread("", "~d ~d"),
- read_input(N - 1, [{X,Y}|Acc]).
- main() ->
- {ok, [N]} = io:fread("", "~d"),
- Points = read_input(N, []),
- Hull = quick_hull(Points),
- io:format("~p~n",[Hull]).
Advertisement
Add Comment
Please, Sign In to add comment