Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- MathContext mathContext = new MathContext(100, RoundingMode.HALF_UP);
- BigDecimal getAngleFactor(int p1, int p2, int[][] points) {
- int x1 = points[p1][0];
- int y1 = points[p1][1];
- int x2 = points[p2][0];
- int y2 = points[p2][1];
- if (x2 == x1) return new BigDecimal(0);
- double r1 = y2 - y1;
- double r2 = x2 - x1;
- BigDecimal r = new BigDecimal(r1).divide(new BigDecimal(r2), mathContext);
- // System.out.println(String.format("%f / %f = %f", r1, r2, r));
- return r;
- }
- BigDecimal getShift(int p1, int p2, int[][] points) {
- int x1 = points[p1][0];
- int y1 = points[p1][1];
- int x2 = points[p2][0];
- int y2 = points[p2][1];
- if (x2 == x1) return new BigDecimal(x1);
- double r1 = x2*y1 - x1*y2;
- double r2 = x2 - x1;
- BigDecimal r = new BigDecimal(r1).divide(new BigDecimal(r2), mathContext);
- // System.out.println(String.format("%f / %f = %f", r1, r2, r));
- return r;
- }
- class Line {
- BigDecimal angleFactor;
- BigDecimal shift;
- Line(int p1, int p2, int[][] points) {
- angleFactor = getAngleFactor(p1, p2, points);
- shift = getShift(p1, p2, points);
- }
- @Override
- public boolean equals(Object object){
- try {
- Line line = (Line)object;
- return line.angleFactor.equals(this.angleFactor) && line.shift.equals(this.shift);
- } catch (NullPointerException | ClassCastException ex) {
- return false;
- }
- }
- @Override
- public int hashCode() {
- return Math.toIntExact(Math.round(angleFactor.doubleValue() * 31 + shift.doubleValue()));
- }
- @Override
- public String toString() {
- return String.format("k = %e, b = %e", angleFactor, shift);
- }
- }
- public int maxPoints(int[][] points) {
- if (points.length < 3) {
- return points.length;
- }
- Map<Line,Set<Integer>> stat = new HashMap<Line,Set<Integer>>();
- for (int i = 0; i < points.length - 1; ++i) {
- for (int j = i + 1; j < points.length; ++j) {
- Line line = new Line(i, j, points);
- // System.out.println(String.format("%s x %s = %s", pointToString(i, points), pointToString(j, points), line));
- Set<Integer> pointSet;
- if (stat.containsKey(line)) {
- pointSet = stat.get(line);
- } else {
- pointSet = new HashSet<Integer>();
- stat.put(line, pointSet);
- }
- pointSet.add(i);
- pointSet.add(j);
- }
- }
- int maxCount = 0;
- for (Map.Entry<Line,Set<Integer>> entry: stat.entrySet()) {
- System.out.println(String.format("%s: %s", entry.getKey(), pointsToString(entry.getValue(), points)));
- maxCount = Math.max(maxCount, entry.getValue().size());
- }
- return maxCount;
- }
- String pointsToString(Set<Integer> pointIndexes, int[][] points) {
- StringBuilder stringBuilder = new StringBuilder();
- stringBuilder.append("{ ");
- for (Integer index : pointIndexes) {
- stringBuilder.append(pointToString(index, points));
- stringBuilder.append(", ");
- }
- if (!pointIndexes.isEmpty()) {
- stringBuilder.delete(stringBuilder.length() - 2, stringBuilder.length());
- }
- stringBuilder.append(" }");
- return stringBuilder.toString();
- }
- String pointToString(int pointIndex, int[][] points) {
- StringBuilder stringBuilder = new StringBuilder();
- stringBuilder.append("{");
- stringBuilder.append(points[pointIndex][0]);
- stringBuilder.append(",");
- stringBuilder.append(points[pointIndex][1]);
- stringBuilder.append("}");
- return stringBuilder.toString();
- }
- public static void main(String[] args) {
- // int[][] points = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
- int[][] points = {{0,0},{94911151,94911150},{94911152,94911151}};
- // int[][] points = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
- Solution solution = new Solution();
- System.out.println(solution.maxPoints(points));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement