package chelper; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.TreeMap; import java.util.TreeSet; import io.InputReader; import io.OutputWriter; import misc.SimpleSavingChelperSolution; public class TaskD extends SimpleSavingChelperSolution { private Comparator sortLeft = new Comparator() { @Override public int compare(Interval o1, Interval o2) { int t = o1.l.compareTo(o2.l); if (t != 0) { return t; } return Integer.compare(o1.i, o2.i); } }; private Comparator sortRight = new Comparator() { @Override public int compare(Interval o1, Interval o2) { int t = o1.r.compareTo(o2.r); if (t != 0) { return t; } return Integer.compare(o1.i, o2.i); } }; public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } class Ratio implements Comparable { long num, denom; public Ratio(long num, long denom) { this.num = num; this.denom = denom; } @Override public int compareTo(Ratio o) { long a = num * o.denom; long b = o.num * denom; return Long.compare(a, b); } } class Interval { Ratio l, r; int i; int order = -1; public Interval(Ratio l, Ratio r, int i) { this.l = l; this.r = r; this.i = i; } } long countOneSide(List intervals) { } @Override public void solve(int testNumber) { int n = in.nextInt(); int maxW = in.nextInt(); List left = new ArrayList<>(); List right = new ArrayList<>(); long res = 0; for (int i = 0; i < n; i++) { int x = in.nextInt(); int v = in.nextInt(); // double minTime = Math.abs(x) / (Math.abs(v) + maxW); // double maxTime = Math.abs(x) / (Math.abs(v) - maxW); Ratio minTime = new Ratio(Math.abs(x), Math.abs(v) + maxW); Ratio maxTime = new Ratio(Math.abs(x), Math.abs(v) - maxW); if (x < 0) { left.add(new Interval(minTime, maxTime, i)); } else { right.add(new Interval(minTime, maxTime, i)); } } Comparator check = new Comparator() { @Override public int compare(Interval o1, Interval o2) { int t = o1.l.compareTo(o2.l); if (t != 0) { return t; } t = o1.r.compareTo(o2.r); return t; } ; }; TreeMap s = new TreeMap<>(check); for (Interval interval : left) { s.putIfAbsent(interval, 0); s.put(interval, s.get(interval) + 1); } for (Integer integer : s.values()) { res += (integer - 1L) * (integer - 0L) / 2; } s = new TreeMap<>(check); for (Interval interval : right) { s.putIfAbsent(interval, 0); s.put(interval, s.get(interval) + 1); } for (Integer integer : s.values()) { res += (integer - 1L) * (integer - 0L) / 2; } TreeSet rightSortLeft = new TreeSet<>(sortLeft); for (Interval interval : right) { rightSortLeft.add(new Interval(interval.l, interval.r, interval.i)); } int howManyLeft = right.size(); for (Interval interval : rightSortLeft) { interval.order = howManyLeft; howManyLeft--; } TreeSet rightSortRight = new TreeSet<>(sortRight); for (Interval interval : right) { rightSortRight.add(new Interval(interval.l, interval.r, interval.i)); } howManyLeft = 0; for (Interval interval : rightSortRight) { howManyLeft++; interval.order = howManyLeft; } for (Interval interval : left) { Interval higher = rightSortLeft.higher(new Interval(interval.r, interval.r, n)); int toRight = 0; if (higher != null) { toRight = higher.order; } Interval lower = rightSortRight.lower(new Interval(interval.l, interval.l, -1)); int toLeft = 0; if (lower != null) { toLeft = lower.order; } res += right.size() - toLeft - toRight; } out.println(res); } }