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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class Fast
{
private int N;
private Point ref;
private Point[] pts;
// reused each iteration
private Point[] work;
private List<Point[]> segments;
// for each slope, the last point must be unique,
// the longest segment is the first to arise
// multiple segment for 1 slope is possible
private HashMap<Double, HashSet<Point>> slopes;
private void addSegment(double sl, int start, int end)
{
// if this solpe is not in the hash yet,
// or the last point is not in the set yet
HashSet slopePoints = slopes.get(sl);
Point last = work[end - 1];
if ((slopePoints == null) || !slopePoints.contains(last))
{
Point[] segment = new Point[end - start + 1];
segment[0] = ref;
for (int k = start, l = 1; k < end; k++, l++)
segment[l] = work[k];
segments.add(segment);
if (slopePoints == null)
{
slopePoints = new HashSet<Point>();
slopePoints.add(last);
slopes.put(sl, slopePoints);
} else
{
slopePoints.add(last);
}
}
}
private void solve(Point[] origin, int len)
{
this.N = len;
this.pts = origin;
work = new Point[N - 1];
segments = new ArrayList<Point[]>();
slopes = new HashMap<Double, HashSet<Point>>();
for (int i = 1, n = N - 1; i < N - 3; i++, n--)
{
// reference [i-1] and copy [i;N[ to [0;n[
ref = pts[i - 1];
for (int k = 0, j = i; k < n; k++, j++)
work[k] = pts[j];
// sort [0;n[
Arrays.sort(work, 0, n, ref.SLOPE_ORDER);
// search for sequences >2 in [0;n[
int start = -1;
double slope = Double.NEGATIVE_INFINITY;
for (int j = 0; j < n; j++)
{
double sl = ref.slopeTo(work[j]);
if (sl == Double.NEGATIVE_INFINITY)
continue;
if (sl != slope)
{
if ((start != -1) && ((j - start) > 2))
addSegment(slope, start, j);
slope = sl;
start = j;
}
}
if ((n - start) > 2)
addSegment(slope, start, n);
}
for (Point[] seg : segments)
{
seg[0].drawTo(seg[seg.length-1]);
String out = "";
for (Point p : seg)
out += p+" -> ";
StdOut.println(out.substring(0, (out.length() - 4)));
}
}
public static void main(String[] args)
{
// Stopwatch w = new Stopwatch();
In in = new In(args[0]);
int n = in.readInt();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.show(0);
Point[] pts = new Point[n];
for (int i = 0; i < n; i++)
{
pts[i] = new Point(in.readInt(), in.readInt());
pts[i].draw();
}
Arrays.sort(pts);
new Fast().solve(pts, n);
// StdOut.printf("Time: %f\n\n", w.elapsedTime());
StdDraw.show(0);
}
}
|
