Advertisement
popov-aa

Untitled

Oct 12th, 2019
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.41 KB | None | 0 0
  1. class Solution {
  2.  
  3.     MathContext mathContext = new MathContext(100, RoundingMode.HALF_UP);
  4.  
  5.     BigDecimal getAngleFactor(int p1, int p2, int[][] points) {
  6.         int x1 = points[p1][0];
  7.         int y1 = points[p1][1];
  8.         int x2 = points[p2][0];
  9.         int y2 = points[p2][1];
  10.         if (x2 == x1) return new BigDecimal(0);
  11.         double r1 = y2 - y1;
  12.         double r2 = x2 - x1;
  13.         BigDecimal r = new BigDecimal(r1).divide(new BigDecimal(r2), mathContext);
  14.         // System.out.println(String.format("%f / %f = %f", r1, r2, r));
  15.         return r;
  16.     }
  17.  
  18.     BigDecimal getShift(int p1, int p2, int[][] points) {
  19.         int x1 = points[p1][0];
  20.         int y1 = points[p1][1];
  21.         int x2 = points[p2][0];
  22.         int y2 = points[p2][1];
  23.         if (x2 == x1) return new BigDecimal(x1);
  24.         double r1 = x2*y1 - x1*y2;
  25.         double r2 = x2 - x1;
  26.         BigDecimal r = new BigDecimal(r1).divide(new BigDecimal(r2), mathContext);
  27.         // System.out.println(String.format("%f / %f = %f", r1, r2, r));
  28.         return r;
  29.     }
  30.  
  31.     class Line {
  32.         BigDecimal angleFactor;
  33.         BigDecimal shift;
  34.  
  35.         Line(int p1, int p2, int[][] points) {
  36.             angleFactor = getAngleFactor(p1, p2, points);
  37.             shift = getShift(p1, p2, points);
  38.         }
  39.  
  40.         @Override
  41.         public boolean equals(Object object){
  42.             try {
  43.                 Line line = (Line)object;
  44.                 return line.angleFactor.equals(this.angleFactor) && line.shift.equals(this.shift);
  45.             } catch (NullPointerException | ClassCastException ex) {
  46.                 return false;
  47.             }
  48.         }
  49.  
  50.         @Override
  51.         public int hashCode() {
  52.             return Math.toIntExact(Math.round(angleFactor.doubleValue() * 31 + shift.doubleValue()));
  53.         }
  54.  
  55.         @Override
  56.         public String toString() {
  57.             return String.format("k = %e, b = %e", angleFactor, shift);
  58.         }
  59.     }
  60.  
  61.     public int maxPoints(int[][] points) {
  62.         if (points.length < 3) {
  63.             return points.length;
  64.         }
  65.  
  66.         Map<Line,Set<Integer>> stat = new HashMap<Line,Set<Integer>>();
  67.         for (int i = 0; i < points.length - 1; ++i) {
  68.             for (int j = i + 1; j < points.length; ++j) {
  69.                 Line line = new Line(i, j, points);
  70.                 // System.out.println(String.format("%s x %s = %s", pointToString(i, points), pointToString(j, points), line));
  71.                 Set<Integer> pointSet;
  72.                 if (stat.containsKey(line)) {
  73.                     pointSet = stat.get(line);
  74.                 } else {
  75.                     pointSet = new HashSet<Integer>();
  76.                     stat.put(line, pointSet);
  77.                 }
  78.                 pointSet.add(i);
  79.                 pointSet.add(j);
  80.             }
  81.         }
  82.  
  83.         int maxCount = 0;
  84.         for (Map.Entry<Line,Set<Integer>> entry: stat.entrySet()) {
  85.             System.out.println(String.format("%s: %s", entry.getKey(), pointsToString(entry.getValue(), points)));
  86.             maxCount = Math.max(maxCount, entry.getValue().size());
  87.         }
  88.  
  89.         return maxCount;
  90.     }
  91.  
  92.     String pointsToString(Set<Integer> pointIndexes, int[][] points) {
  93.         StringBuilder stringBuilder = new StringBuilder();
  94.         stringBuilder.append("{ ");
  95.         for (Integer index : pointIndexes) {
  96.             stringBuilder.append(pointToString(index, points));
  97.             stringBuilder.append(", ");
  98.         }
  99.         if (!pointIndexes.isEmpty()) {
  100.             stringBuilder.delete(stringBuilder.length() - 2, stringBuilder.length());
  101.         }
  102.         stringBuilder.append(" }");
  103.         return stringBuilder.toString();
  104.     }
  105.  
  106.     String pointToString(int pointIndex, int[][] points) {
  107.         StringBuilder stringBuilder = new StringBuilder();
  108.         stringBuilder.append("{");
  109.         stringBuilder.append(points[pointIndex][0]);
  110.         stringBuilder.append(",");
  111.         stringBuilder.append(points[pointIndex][1]);
  112.         stringBuilder.append("}");
  113.         return stringBuilder.toString();
  114.     }
  115.  
  116.     public static void main(String[] args) {
  117.         // int[][] points = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
  118.         int[][] points = {{0,0},{94911151,94911150},{94911152,94911151}};
  119.         // int[][] points = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
  120.         Solution solution = new Solution();
  121.         System.out.println(solution.maxPoints(points));
  122.     }
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement