4 Values whose Sum is 0

Условие

Дан набор отрезков на плоскости. Требуется определить количество различных пар перекрывающихся отрезков. Два отрезка считаются перекрывающимися, если они имеют бесконечное число общих точек.

Ограничения

Количество отрезков от 1 до 100000. Координаты концов отрезков являются целыми числами, лежащими в диапазоне от 0 до 100000. Ограничение на время работы – 6 секунд, на память – 64 Мб.

Пример входного файла Пример выходного файла
2
8
1 1 2 2
2 2 3 3
1 3 3 1
10 0 20 0
20 0 30 0
15 0 25 0
50 0 100 0
70 0 80 0
1
0 0 1 1
Scenario #1:
3

Scenario #2:
0

Источник: TUD Programming Contest 2005.

Решение

Анализ

Сначала определим, когда два отрезка имеют бесконечное число общих точек. Очевидно, что это возможно только в том случае, если они лежат на одной прямой и хотя бы один конец любого отрезка лежит строго внутри другого отрезка. Отсюда сразу вытекает простейшее решение задачи: перебор всех пар и проверка вышеописанных условий. Его сложность O(N^2), где N – число отрезков.

При указанных ограничениях на N (до 10^5) данное решение не подходит. Можно сразу выделить основной недостаток данного алгоритма: в нем не учитывается взаимное расположение отрезков. Очевидно, что зафиксировав отрезок, дальше следует рассматривать только те отрезки, которые лежат на той же прямой. Устранение этого недостатка лежит в основе решения данной задачи.

Решение

Решение состоит из двух этапов:

  1. группировка отрезков, лежащих на одной прямой;
  2. подсчет числа пар перекрывающихся отрезков для каждой группы.
Этап 1. Группировка отрезков

Во-первых, для каждого отрезка восстанавливаются коэффициенты уравнения прямой, по известным формулам.

Далее, уравнения следует преобразовать, так чтобы уравнения, описывающие одинаковые прямые имели одинаковые коэффициенты. В данной задаче, коэффициенты могут быть только целыми, поэтому проще всего сократить их на НОД, и домножить на -1, если при первый ненулевой коэффициент отрицателен. Легко проверит, что данные преобразования корректны. И теперь, отрезки можно сгруппировать по уравнениям прямых, на которых они лежат. Для этого можно использовать сортировку, бинарное дерево или хэш-таблицу. Временная сложность данного этапа зависит от выбранного метода группировки (при использовании быстрой сортировки – O(N logN)).

Этап 2. Подсчет ответа

Пусть зафиксирована группа отрезков, лежащих на одной прямой. Необходимо подсчитать число перекрывающихся пар отрезков быстрее чем за O(N^2).

Во-первых, можно выполнить такое преобразование плоскости, что прямая на которой лежат отрезки совпадет с OX. Теперь, все концы отрезков будут описываться одной координатой, по которой их можно отсортировать и ввести понятия левого и правого конца. Причем сортировку следует выполнять так, чтобы в случае совпадения координаты, сначала шли правые концы, а затем левые. После этого следует применить метод сканирующей прямой. Будем перебирать концы в порядке увеличения координаты. При этом будем поддерживать количество «открытых» отрезков, то есть отрезков, у которых уже рассмотрен левый конец, но еще не встретился правый. Если текущий конец левый, то к ответу следует прибавить количество открытых отрезков (не учитывая текущий). В результате получим общее число пар перекрывающихся отрезков лежащих на данной прямой.

Чтобы убедится в корректности данного метода подсчета, рассмотрим его подробнее. Когда мы встречаем левый конец, то все правые концы с меньшей или равной координатой обработаны. Другими словами, текущий левый конец лежит строго внутри всех открытых на данный момент отрезков, количество которых прибавляется к ответу. Легко заметить, что пока, возможно, учтены не все пары с данным отрезком. Однако, при обработке других левых концов, которые встретятся до правого конца текущего будут учтены оставшиеся пары.

Очевидно, что описанный алгоритм без учета сортировки работает за линейное время. В итоге, второй этап работает за O(N logN), если использовать быструю сортировку.

Реализация

Следует воспользоваться тем, что входные данные – целые числа, так как это значительно упростит многие сравнения, и избавит от погрешности вычислений. Дробные числа в вышеописанном решении появляются на втором этапе, при преобразовании плоскости. Данное преобразование можно не выполнять, а рассматривать лишь проекцию прямой на OX (или OY, в случае если проекция вырождается в точку). Легко проверить, что это корректно и не влияет на дальнейший ход решения.

Приведем решение на Java:

0000: import java.io.*;
0001: import java.util.*;
0002:
0003: import static java.lang.Math.*;
0004: import static java.util.Arrays.sort;
0005:
0006: public class Main {
0007:     public static void main(String[] args) throws IOException {
0008:         new Main().run();
0009:     }
0010:
0011:     BufferedReader in;
0012:     PrintWriter out;
0013:     
0014:     void run() throws IOException {
0015:         in = new BufferedReader(new InputStreamReader(System.in));
0016:         out = new PrintWriter(System.out);
0017:         for (int i = 0; i < segments.length; i++) segments[i] = new Line();
0018:         for (int i = 0; i < events.length; i++) events[i] = new Event();
0019:         for (int testNum = Integer.parseInt(in.readLine()), testCase = 1; testCase <= testNum; testCase++)
0020:             solveCase(testCase);
0021:         out.close();
0022:     }
0023:     
0024:     int MAXN = 100000;
0025:
0026:     int segNum;
0027:     int evntNum;
0028:     
0029:     Line[] segments = new Line [MAXN];
0030:     Event[] events = new Event [2 * MAXN];
0031:     
0032:     long ans;
0033:     
0034:     void solveCase(int testCase) throws IOException {
0035:         int segNum = Integer.parseInt(in.readLine());
0036:         for (int seg = 0; seg < segNum; seg++) {
0037:             StringTokenizer tok = new StringTokenizer(in.readLine());
0038:             segments[seg].set(Integer.parseInt(tok.nextToken()), Integer.parseInt(tok.nextToken()), Integer.parseInt(tok.nextToken()), Integer.parseInt(tok.nextToken()));
0039:         }
0040:         sort(segments, 0, segNum);
0041:         evntNum = 0;
0042:         Line base = segments[0];
0043:         ans = 0L;
0044:         for (int seg = 0; seg < segNum; seg++) {
0045:             Line cs = segments[seg];
0046:             if (base.A == cs.A && base.B == cs.B && base.C == cs.C) {
0047:                 events[evntNum++].set( 1, cs.A == 0 ? min(cs.p1.x, cs.p2.x) : min(cs.p1.y, cs.p2.y));
0048:                 events[evntNum++].set(-1, cs.A == 0 ? max(cs.p1.x, cs.p2.x) : max(cs.p1.y, cs.p2.y));
0049:             } else {
0050:                 count();
0051:                 evntNum = 0;
0052:                 base = segments[seg--];
0053:             }
0054:         }
0055:         count();
0056:         out.println("Scenario #" + testCase + ":\n" + ans + "\n");
0057:     }
0058:     
0059:     void count() {
0060:         int bal = 0;
0061:         sort(events, 0, evntNum);
0062:         for (int en = 0; en < evntNum; en++) {
0063:             Event e = events[en];
0064:             if (e.type == 1)
0065:                 ans += bal;
0066:             bal += e.type;
0067:         }
0068:     }
0069:
0070:     int gcd(int a, int b) {
0071:         a = abs(a);
0072:         b = abs(b);
0073:         while (a > 0 && b > 0)
0074:             if (a > b)
0075:                 a %= b;
0076:             else
0077:                 b %= a;
0078:         return a + b;
0079:     }
0080:     
0081:     class Point {
0082:         int x;
0083:         int y;
0084:         
0085:         void set(int x, int y) {
0086:             this.x = x;
0087:             this.y = y;
0088:         }
0089:     }
0090:     
0091:     class Line implements Comparable {
0092:         Point p1 = new Point();
0093:         Point p2 = new Point();
0094:         int A;
0095:         int B;
0096:         int C;
0097:         
0098:         void set(int x1, int y1, int x2, int y2) {
0099:             p1.set(x1, y1);
0100:             p2.set(x2, y2);
0101:             A = p2.y - p1.y;
0102:             B = p1.x - p2.x;
0103:             
0104:             int gcd = gcd(A, B);
0105:             A /= gcd;
0106:             B /= gcd;
0107:             C = -(A * p1.x + B * p1.y);
0108:             
0109:             if (A < 0 || A == 0 && (B < 0 || B == 0 && C < 0)) {
0110:                 A = -A;
0111:                 B = -B;
0112:                 C = -C;
0113:             }
0114:         }
0115:
0116:         @Override
0117:         public int compareTo(Line l) {
0118:             if (A != l.A) return A < l.A ? -1 : 1;
0119:             if (B != l.B) return B < l.B ? -1 : 1;
0120:             if (C != l.C) return C < l.C ? -1 : 1;
0121:             return 0;
0122:         }
0123:     }
0124:     
0125:     class Event implements Comparable {
0126:         int type;
0127:         int time;
0128:
0129:         void set(int type, int time) {
0130:             this.type = type;
0131:             this.time = time;
0132:         }
0133:
0134:         @Override
0135:         public int compareTo(Event e) {
0136:             if (time != e.time) return time < e.time ? -1 : 1;
0137:             if (type != e.type) return type < e.type ? -1 : 1;
0138:             return 0;
0139:         }
0140:     }
0141: }