Test the best
Порой атмосфера в компьютерной лаборатории напоминает собой библиотеке...
далее
Сегодня нашими собеседниками являются ведущие разработчики белорусской...
далее
У сегодняшнего лидера рейтинга TTB Алексея Данченко aka DAle сейчас до...
далее
 
 
новости ИТ
СПОНСОРЫ
EPAM Systems
генеральный спонсор
ServiceWare Technologies
ПАРТНЕРЫ
белорусский портал TUT.by
революционная баннерная сеть Red.by
"Компьютерные Вести On-line"
Спонсор доступа в интернет компания Solo
портал белорусских программистов
Первый Белорусский Linux-портал
НОВОСТИ САЙТА
  Разбор задачи "Ковровая бомбардировка"

Так как в задаче нам необходимо будет работать с прямыми, то для начала полезно научиться проводить прямую через две точки. Общеизвестно, что прямая, проходящая через две различные точки (x1, y1) и (x2, y2) задается уравнением Ax + By + C = 0, где A = y2 - y1, B = x1 - x2, C = - Ax1 - By1. Однако, одну и ту же прямую можно задать в виде Ax + By + C = 0 бесконечным количеством способов (можно просто одновременно умножать коэффициенты A, B, C на различные ненулевые константы). Для введения унифицированного способа задания прямой можно сначала после подсчета коэффициентов A, B, C разделить их на НОД(|A|, |B|) (это можно сделать, если A, B, C - целые числа, в частности, если координаты точек, по которым строится прямая, целые). Это не устраняет неоднозначности, но теперь у прямой остается только два способа задания, отличающиеся только знаком. Чтобы избавиться от этого, можно наложить на коэффициенты A и B условие (A > 0) или ((A = 0) и (B > 0)), и, если оно не выполняется, то домножить коэффициенты A, B, C на -1. Описанный способ, конечно, не является единственным способом однозначного задания прямой, однако его несомненным достоинством является то, что прямая задается целыми, а не вещественными числами, и мы застрахованы от погрешностей вычислений с плавающей точкой.

Следующее, что следует отметить - это то, что в оптимальном решении, хотя бы одна прямая проходит хотя бы через две из заданных точек. Поэтому логично провести через все пары точек прямые, и работать с ними. Итак, мы получили n(n+1) / 2 прямых, где n - количество точек. Каждая такая прямая задает некоторое направление для бомбардировки, и среди всех этих направлений нужно выбрать оптимальное. Некоторые прямые могут задавать одно и то же направление, поэтому, чтобы не проверять одинаковые направления по нескольку раз, полезно вначале выделить все различные направления, которые у нас имеются. Две прямые задают одно и то же направление, когда они параллельны, то есть их коэффициенты A и B совпадают. Таким образом, нам необходимо сгруппировать прямые с одинаковыми значениями A и B. Простой способ быстрого проведения такой группировки - сортировка прямых. Более точно, можно ввести отношение сравнения прямых: прямая A1x + B1y + C1 = 0 считается меньше прямой A2x + B2y + C2 = 0, если (A1 < A2) или ((A1 = A2) и (B1 < B2)), и отсортировать прямые в соответствии с этим отношением. При этом параллельные прямые расположатся в отсортированном массиве рядом друг с другом, и прямые будет легко разделить на группы.

Теперь, после того, как все направления выбраны, осталось только научиться определять, сколько прямых понадобится для того, чтобы покрыть все точки в прямыми в данном направлении. На первый взгляд, количество прямых равно это количество равно количеству различных коэффициентов C в группе прямых, определяющих данное направление, но это не совсем так, потому что могут быть одиночные точки, не покрытые ни одной из прямых в группе, для покрытия каждой из которых необходима дополнительная прямая. Подсчитать количество различных коэффициентов C в группе можно, действуя аналогично как при разделении направлении, то есть отсортировав прямые по коэффициенту C. Для подсчета количества непокрытых одиночных точек нужно действовать немного хитрее. Основная идея заключается в том, что, если некоторая прямая покрывает сразу m точек, то эта прямая будет встречаться в m(m+1) / 2 копиях. По числу m(m+1) / 2 можно легко восстановить m. После сортировки прямых по C, мы сгруппируем одинаковые прямые. Для каждой группы мы можем узнать количество точек, которые покрывает данная прямая. Просуммировав эти количества по всем прямым, мы узнаем общее количество покрытых, а, следовательно, и непокрытых точек.

Описанному решению для обработки n точек необходимо порядка n2 log n операций. Приведенная ниже реализация на Java работает в сумме на всех тестах около 15 секунд.

import java.util.*;

class Line {
    public int a, b, c;

    public Line(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

class LineComparator implements Comparator {
    public int compare(Object a, Object b) {
        Line _a = (Line)a;
        Line _b = (Line)b;
        if (_a.a != _b.a) {
            return _a.a - _b.a;
        } else
        if (_a.b != _b.b) {
            return _a.b - _b.b;
        } else {
            return _a.c - _b.c;
        }
    }
}

public class Bombing {
    public int gcd(int a, int b) {
        while ((a != 0) && (b != 0)) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
        }
        return a+b;
    }

    public int getMinimum(int[] x, int[] y) {
        int n = x.length;
        Line[] lines = new Line[(n * (n-1)) / 2];
        int cnt = 0;

        for (int i=0; i+1 < n; i++) {
            for (int j=i+1; j < n; j++) {
                int a = y[j] - y[i];
                int b = x[i] - x[j];
                int c = -a * x[i] - b * y[i];

                if ((a < 0) || ((a == 0) && (b < 0))) {
                    a = -a;
                    b = -b;
                    c = -c;
                }

                int d = gcd(Math.abs(a), Math.abs(b));
                a /= d;
                b /= d;
                c /= d;

                lines[cnt++] = new Line(a, b, c);
            }
        }

        Arrays.sort(lines, new LineComparator());

        int[] points = new int[(n * (n-1)) / 2 + 1];
        for (int i=2; i <= n; i++) {
            points[(i * (i-1)) / 2] = i;
        }

        int best = n;
        int cur = n;
        int left = 0;
        int curline = 0;

        for (int i=0; i < cnt; i++) {
            if ((i == 0) || (lines[i].a != lines[i-1].a) || 
                (lines[i].b != lines[i-1].b) || 
                (lines[i].c != lines[i-1].c)) {
                if (curline > 0) {
                    left -= points[curline];
                    cur++;
                }
                curline = 0;
            }
            if ((i == 0) || (lines[i].a != lines[i-1].a) || 
                (lines[i].b != lines[i-1].b)) {
                best = Math.min(best, cur + left);
                cur = 0;
                left = n;
            }
            curline++;
        }

        left -= points[curline];
        cur++;
        best = Math.min(best, cur + left);

        return best;
    }
}



назад на все новости сайта   

РЕКЛАМА
ВХОД
Логин:
Пароль:
Регистрация
Забыли пароль?
ОПРОС
Что является основным стимулом для игры на TTB?

приз
попасть в рейтинг
интерес
поупражнять мозги
слава :)
OK
все опросы
РЕЙТИНГ
1.   DAle -  328
2.   Zis -  300
3.   forest -  270
4.   HeaDacHe -  226
5.   Orlangur -  213
6.   Punk -  170
7.   Crush -  167
8.   may -  114
9.   Monk -  85
10.   One -  79
весь рейтинг
ГОРЯЧИЕ ТЕМЫ
Анонс 2-ого этапа главного кон
1-й этап главного конкурса
Вычисление рейтинга (обсуждени
Юрий Чайков и Юрий Пачковский
Приглашаем на работу разработч
все форумы
Главная   |  Конкурсы  | Новости  | Статьи  | Сообщество  | Форумы  | ВУЗы  | О проекте
Проект Test The Best (c) 2004-2005
Генеральный спонсор: EPAM systems
Спонсор доступа в интернет компания Solo
Перепечатка оригинальных материалов Test The Best приветствуется при наличии ссылки
Rambler's Top100 Rating All.BY Каталог TUT.BY