elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
[topcoder SRM 250] В меру сложно и разнообразно
elizarov
В общем и целом, topcoder SRM 250 оказался интересным и в меру сложным ;) А сдал решение последней задачки буквально за 5 минут до окончания. Чудом решив все задачи правильно я оказался на 6-м месте в общей таблице результатов, что сильно подняло мой рейтинг (до 2215).

Первая задачка была простой, но с подковыркой. Я был уверен, что решение в double-ах пройдет, но, признаюсь, не сильно напрягал голову когда выбирал 1e-9 в качестве эпсилона. К счастью, этого было достаточно.

Над второй задачкой пришлось подумать. Быстро отбросив идеи про жадный алгоритм (не зря я перечитывал теорию матроидов) я придуман динамический алгоритм и приступил к написанию кода. Однако трудность меня подстерегала при вводе данных. Я стал дико тупить и минут 5 не мог сообразить что означает AM/PM нотация для времени. Пытался тщетно сообразить что же именно значит 12:35PM и 12:35AM. Эти потуги происходили когда я уже набил код для разбора строчек вида hh:mmaa самостоятельно. У меня уже было целое число от 1 до 12 обозначающее час, целое число от 0 до 59 обозначающее минуты и флаг AM/PM. Уверенность что я что-то понял у меня так и не появилась, и я удалил написанный код парсинга, поручив всю работу стандартным классам в Java: calendar.setDate(new SimpleDateFormat(“hh:mmaa”).parse(s)). А дальше – calendar.get(Calendar.HOUR_OF_DAY) и calendar.get(Calendar.MINUTE).

Третья задачка была чистой геометрией. Здесь всё было в технике и аккуратности кодирования. На первом этапе надо было найти все точки результирующего многоугольника. Написав этот код, мне пришлось его отлаживать (было несколько опечаток в математике пересечений). Когда отладка была закончена, и у меня был правильный список точек, я просто скопировал свое решение задачки из предыдущего соревнования, которое находит площадь выпуклой оболочки. В первой части решения (ввод данных и нахождение пересечений) я слишком активно пользовался cut-and-paste-ом. Если бы я программировал более структурно (завел бы класс Polygon с методами чтения и проверки точки на принадлежность), то это бы сильно упростило и ускорило бы процесс отладки.

  • 1
Если я не заблуждаюсь жестоко, то 12 часов в нотации c AM/PM нужно просто трактовать как ноль.

Правильное решение третьей задачи - через java.awt.geom.*...

Про AM/PM всё именно так. Теперь я это запомню на долго :)

Про java.awt.geom.* я знал, но никогда не использовал. Внимательно же изучать новый для себя API это совсем не то, что хочется делать в пылу соревнования. Надежней делать то, что уже умеешь, а геометрию писать я (в целом) умею писать и сам. Однако жаль, что в java.awt.geom.Area нет стандартного метода собственно для подсчета площади. Его приходится писать самому, а это получается уже не так красиово (занимает много места). Кстати, очень странно, что после использования метода intersect он выдает точки по часовой стрелеке. Документация на этот счет вообще молчит, поэтому для надежности я исплоьзовал Math.abs при подсчете площади. Получается вот такое вот решение:

public class ConvexPolygons {
	public double overlap(String[] polygon1, String[] polygon2) {
		Area a = read(polygon1);
		a.intersect(read(polygon2));
		double res = 0;
		double[] c = new double[6];
		double x0 = Double.NaN;
		double y0 = Double.NaN;
		double x = Double.NaN;
		double y = Double.NaN;
		for (PathIterator pi = a.getPathIterator(new AffineTransform()); !pi.isDone(); pi.next()) {
			switch (pi.currentSegment(c)) {
			case PathIterator.SEG_MOVETO:
				x = x0 = c[0];
				y = y0 = c[1];
				break;
			case PathIterator.SEG_LINETO:
				res += (x - c[0]) * (y + c[1]);
				x = c[0];
				y = c[1];
				break;
			case PathIterator.SEG_CLOSE:
				res += (x - x0) * (y + y0);
				break;
			default:
				throw new IllegalArgumentException();
			}
		}
		return 0.5 * Math.abs(res);
	}

	private Area read(String[] s) {
		GeneralPath gp = new GeneralPath();
		for (int i = 0; i < s.length; i++) {
			StringTokenizer st = new StringTokenizer(s[i]);
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			if (i == 0)
				gp.moveTo(x, y);
			else
				gp.lineTo(x, y);
		}
		gp.closePath();
		return new Area(gp);
	}
}


Признаюсь честно, я всего лишь изучаю решения победителей:) Мне кажется, что там площадь считается красивее:)

Если у тебя координаты точек находятся в массиве (а не берутся из PathIterator-а), то конечно красивей ;) Или ты имеешь в виду решение Psycho? Там используется java.awt.geom.* и нахождение площади дейтствительно короче.

При ближайшем рассмотрении выясняется что они все ищут площадь многоугольника с помощью треугольников (так их учат на topcoder-овском сайте), а меня в школе учили делать это через трапеции. Если же делать через треугольники, то в данном случае действительно получается более красивый код, так как не нужно специально обрабатывать случай последней точки. Можно написать что-то типа вот этого (навеяно решением Psycho):

		double res = 0;
		double[] c = new double[6];
		PathIterator pi = a.getPathIterator(null);
		if (pi.isDone())
			return 0;
		pi.currentSegment(c);
		double x0 = c[0];
		double y0 = c[1];
		double x = x0;
		double y = y0;
		for (; pi.currentSegment(c) != PathIterator.SEG_CLOSE; pi.next()) {
			res += (x - x0) * (c[1] - y0) - (y - y0) * (c[0] - x0);
			x = c[0];
			y = c[1];
		}
		return 0.5 * Math.abs(res);

Исправление: Имел в виду решение Psyho

  • 1
?

Log in

No account? Create an account