Commits

Andrew Kozlov committed 6f4f455 Merge

Merged in shagal/evaluator-tasks (pull request #10)

Comments (0)

Files changed (21)

cg2012.1/08-points_in_cell_general/checker/CMakeLists.txt

+cmake_minimum_required(VERSION 2.6)
+
+project(pointsincellgeneral-checker)
+
+set(sources checker.cpp)
+add_definitions(-O2 -frounding-math)
+link_libraries(CGAL gmp)
+add_executable(points_in_cell_general_checker ${sources})

cg2012.1/08-points_in_cell_general/checker/checker.cpp

+#include <vector>
+#include <iostream>
+#include <fstream>
+#include <algorithm>
+
+#include <CGAL/Gmpq.h>
+typedef CGAL::Gmpq gmp;
+
+void onedim(std::vector<std::vector<gmp>>& points, gmp val1, gmp val2){
+	std::sort(points.begin(), points.end());
+	std::vector<gmp> current(points.size());
+	for(int i = 0; i < points.size(); i++){
+		current[i] = points[i][0];
+	}
+	int a = std::lower_bound(current.begin(), current.end(), val1) - current.begin();
+	int b = std::upper_bound(current.begin(), current.end(), val2) - current.begin();
+	for(int i = 0; i < points.size(); i++){
+		std::rotate(points[i].begin(), points[i].begin() + 1, points[i].end());
+	}
+	
+	points.erase(points.begin() + b, points.end());
+	points.erase(points.begin(), points.begin() + a);
+
+}  
+
+int main(int argc, char* argv[]){
+	std::ifstream in(argv[1]);
+	int d;
+	in >> d;
+
+	std::vector<std::pair<gmp, gmp>> dcels(d);
+	for(int i = 0; i < d; i++){
+		double a;
+		double b;
+		in >> a;
+		dcels[i].first = gmp(a);
+	}
+
+	for(int i = 0; i < d; i++){
+		double a;
+		double b;
+		in >> a;
+		dcels[i].second = dcels[i].first + gmp(a);
+	}
+
+
+	int n;
+	in >> n;
+	std::vector<std::vector<gmp>> points;
+	for(int i = 0; i < n; i++){
+		std::vector<gmp> current(d);
+		double val;
+		for(int j = 0; j < d; j++){
+			in >> val;
+			current[j] = gmp(val);
+		}
+		points.push_back(current);
+	}
+	
+	std::vector<std::vector<gmp>> pointsstart = points;
+	
+	int dim = d;
+	int i = 0;
+	while((dim > 0) && points.size() != 0){
+		onedim(points, dcels[i].first, dcels[i].second);
+		i++;
+		dim--;
+	}
+
+	
+	std::vector<int> answer;
+	if(points.size() == 0){
+		answer.push_back(-1);
+	} else {
+		for(int i = 0; i < points.size(); i++){
+			for(int j = 0; j < pointsstart.size(); j++){
+				if(points[i] == pointsstart[j]){
+					answer.push_back(j + 1);
+				}
+			}
+		}
+	}
+	std::sort(answer.begin(), answer.end());
+	in.close();
+	
+	
+	
+	std::ifstream input(argv[2]);
+
+	int nans;
+	input >> nans;
+	std::vector<int> ans;
+	int cur = -1;
+	for(int i = 0; i < nans; i++){
+		input >> cur;
+		ans.push_back(cur);
+	}
+
+	input.close();
+	
+	
+	if(ans.size() != answer.size()){
+		return 1;
+	}
+
+	std::sort(ans.begin(), ans.end());
+	
+	
+	for(int i = 0; i < nans; i++){
+		if(ans[i] != answer[i]){
+			return 1;
+		}
+	}	
+	
+	return 0;
+}

cg2012.1/08-points_in_cell_general/statement/points_in_cell_general.tex

 
 ������ ������ �������� ����� �������� ����� ����� $d$ --- �����������
 ������������. ������ ������ �������� $a_1, a_2, \ldots a_d$ --- ����������
-�����, �������� ������. ������ ������ �������� $d$ ������������ ����� $l_1, l_2, \ldots l_d$ --- ����� ������ ������. ��������� ������� �������� ��
+�����, �������� ������. ������ ������ �������� $d$ ������������ ����� $l_1, l_2, \ldots l_d$ --- ����� ������ ������. ��������� ������ �������� ����� ����� $n$ --- ���������� �����. ��������� $n$ ����� �������� ��
 $d$ ����� --- ���������� �����.
 
 \OutputFile
 2
 0 0
 2 2
+6
 0 8
 1 6
 1.5 1.5

cg2012.1/08-points_in_cell_general/statement/statement.pdf

Binary file modified.

cg2012.1/08-points_in_cell_general/testgen/TestGen8.java

+import java.io.FileNotFoundException;
+import java.io.PrintWriter;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import static java.lang.Math.abs;
+
+/**
+ * Created by IntelliJ IDEA.
+ * User: ррр
+ * Date: 26.04.12
+ * Time: 20:09
+ * To change this template use File | Settings | File Templates.
+ */
+
+public class TestGen8 {
+
+    public static void main(String[] args) throws FileNotFoundException {
+        generate(0, 20);
+        generate(1, 3);
+    }
+
+    private static void generate(int task, int count) throws FileNotFoundException {
+        Random random = new Random();
+
+        PrintWriter printWriter;
+        String fileName, stringFormat;
+        int n, m;
+
+        if (task == 0) {
+            fileName = "correctness_tests/";
+            stringFormat = "%02d";
+            n = random.nextInt(50);
+            m = random.nextInt(200);
+
+        } else {
+            fileName = "performance_tests/";
+            n = 10;
+            m = 1000;
+            stringFormat = "%03d";
+        }
+
+        for (int i = 0; i < count; i++) {
+            String s = fileName + String.format(stringFormat, i + 1) + ".in";
+            printWriter = new PrintWriter(s);
+
+            write(printWriter, n, m);
+        }
+    }
+
+    static void write(PrintWriter out, int dmax, int nmax){
+        Random random = new Random();
+
+        int d = abs(random.nextInt(dmax) + 1);
+        List<Double> a = new ArrayList<Double>();
+        out.println(d);
+        for(int i = 0; i < d; i++){
+            a.add((abs(random.nextInt(150)) + 1) * nextDouble());
+            out.print(a.get(a.size() - 1) + " ");
+        }
+        out.println();
+
+        for(int i = 0; i < d; i++){
+            out.print(nextDouble(a.get(i), a.get(i) + 100) + " ");
+        }
+
+        int n = random.nextInt(nmax) + 10;
+
+        out.println();
+        out.println(n);
+        for(int i = 0; i < n; i++){
+            out.println();
+            for(int j = 0; j < d; j++){
+                out.print(nextDouble(0, random.nextInt(150) + 100) + " ");
+            }
+        }
+        out.close();
+    }
+    static double nextDouble(double start, double finish){
+        Random random = new Random();
+
+        if(finish < start){
+            double tmp = start;
+            start = finish;
+            finish = tmp;
+        }
+        return start + random.nextDouble()*(finish - start);
+    }
+    static double nextDouble(){
+        return nextDouble(0, 1);
+    }
+}

cg2012.1/08-points_in_cell_general/testgen/correctness_tests/readme

+Этот файл нужен только потому, что mercurial не умеет отслеживать пустые папки, создать папку на плюсах просто только с помощью буста.

cg2012.1/08-points_in_cell_general/testgen/performance_tests/readme

+Этот файл нужен только потому, что mercurial не умеет отслеживать пустые папки, создать папку на плюсах просто только с помощью буста.

cg2012.1/15-segment_set_intersection/checker/CMakeLists.txt

+cmake_minimum_required(VERSION 2.6)
+
+project(segmentsetintersection-checker)
+
+set(sources checker.cpp)
+add_definitions(-O2 -frounding-math)
+link_libraries(CGAL gmp)
+add_executable(segment_set_intersection_checker ${sources})

cg2012.1/15-segment_set_intersection/checker/checker.cpp

+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <algorithm>
+#include <iterator>
+#include <map>
+
+#include <CGAL/Polygon_2_algorithms.h>
+#include <CGAL/Cartesian.h>
+#include <CGAL/Gmpq.h>
+#include <CGAL/intersection_2.h>
+
+typedef CGAL::Gmpq gmp;
+typedef CGAL::Cartesian<gmp> Kernel;
+typedef Kernel::Point_2 Point;
+typedef Kernel::Segment_2 Segment;
+typedef CGAL::Object Object;
+
+using std::vector;
+using std::cin;
+using std::cout;
+using std::cerr;
+using std::ifstream;
+using std::ofstream;
+
+int n;
+vector<Point> allintersections;
+vector<Segment> all;
+
+bool isSeg(const Object& obj){
+	if(const CGAL::Segment_2<Kernel> *ipoint = CGAL::object_cast<CGAL::Segment_2<Kernel> >(&obj)){
+		return true;
+	}
+	return false;
+}
+
+bool isPoint(const Object& obj){
+	if(const CGAL::Point_2<Kernel> *ipoint = CGAL::object_cast<CGAL::Point_2<Kernel> >(&obj)){
+		return true;
+	}
+	return false;
+}
+
+void fill(){
+	ofstream output1("seg.txt");
+	
+	ofstream output2("point.txt");
+	for(int i = 0; i < n; i++){
+		for(int j = 0; j < i; j++){
+			if(i != j){
+				if(do_intersect(all[i], all[j])){
+					Object result = intersection(all[i], all[j]);
+					if(isSeg(result)){
+						Segment seg = CGAL::object_cast<CGAL::Segment_2<Kernel> >(result);
+						output1 << seg << "\n";
+						allintersections.push_back(seg.source());
+						allintersections.push_back(seg.target()); 
+					}
+					if(isPoint(result)){
+						Point p = CGAL::object_cast<CGAL::Point_2<Kernel> >(result);
+						output2 << p << "\n"; 
+						allintersections.push_back(p);
+					}
+				}
+			}
+		}
+	}
+}
+
+vector<std::pair<Point, vector<int>>> generate(){
+	vector<std::pair<Point, vector<int>>> result;
+	
+	for(int i = 0; i < allintersections.size(); i++){
+		vector<int> curresult;
+		for(int j = 0; j < all.size(); j++){
+			if(all[j].has_on(allintersections[i])){
+				curresult.push_back(j+1);
+			}
+		}
+		std::sort(curresult.begin(), curresult.end());
+		if(!curresult.empty()){
+			result.push_back(std::make_pair<Point, vector<int>>(allintersections[i], curresult));
+		}
+	}
+
+	std::sort(result.begin(), result.end());
+	
+	int i = 0;
+	while(i < result.size()){
+		int j = i;
+		while(result[i].first == result[j].first){
+			j++;
+			if(j >= result.size()){
+				break;
+			}
+		}
+		j--;
+		result.erase(result.begin() + i, result.begin() + j);
+		i = i + 1;
+	} 
+	return result; 
+}
+
+bool compare(const vector<int>& a, const vector<int>& b){
+	if(a.size() != b.size()){
+		return false;
+	}
+	for(int i = 0; i < a.size(); i++){
+		if(a[i] != b[i]){
+			return false;
+		}
+	}
+	return true;
+}
+
+int main(int argc, char* argv[]){
+	ifstream in(argv[1]);
+	in >> n;
+	double x;
+	double y;
+	double x1;
+	double y1;
+	for(int i = 0; i < n; i++){
+		in >> x >> y >> x1 >> y1;
+		all.push_back(Segment(Point(x, y), Point(x1, y1)));
+	}
+	
+	fill();
+	
+	vector<std::pair<Point, vector<int>>> trueanswer = generate();
+	in.close();
+
+	ifstream input(argv[2]);
+	int wronganswer = 0;
+
+	int count = 0;
+	input >> count;
+	if(count != trueanswer.size()){
+		wronganswer++;
+	}
+
+	vector<vector<int>> answer(count);
+	for(int i = 0; i < count; i++){
+		int n = 0;
+		input >> n;
+		for(int k = 0; k < n; k++){
+			int cur;
+			input >> cur;
+			answer[i].push_back(cur);
+		}
+		std::sort(answer[i].begin(), answer[i].end());
+	}
+	
+	
+	for(int i = 0; i < answer.size(); i++){
+		bool flag = true;
+		for(int j = 0; (j < trueanswer.size() && flag); j++){
+			if(compare(answer[i], trueanswer[j].second)){
+				trueanswer.erase(trueanswer.begin() + j);
+				flag = false;
+			}
+		}
+		if(flag){
+			wronganswer++;
+		}
+	}
+
+	if((wronganswer == 0) && (trueanswer.size() != 0)){
+		wronganswer++;
+	}
+	  
+	if(wronganswer != 0){
+		return 1;
+	} else {
+		return 0;
+	}
+}

cg2012.1/15-segment_set_intersection/statement/olymp.sty

+%
+% Macros for the contest problems
+% for MikTeX: use latex.exe
+% (C) Dmitry S. Lomov (SPb SU Training Centre), 2001-2002
+% (C) Kitten Computing [Andrew Lopatin & Nick Durov], 2001-2002,2003
+% (C) Andrew Stankevich (SPb IFMO Training Center), 2003,2004
+%
+%
+% This is work in progress, please do not try to modify it.
+% 
+% Visit http://neerc.ifmo.ru/develop/olymp-sty/index.html for
+% project details.
+%
+
+\ProvidesPackage{olymp}
+
+
+\newif\if@landscape\@landscapefalse
+\newif\if@russian\@russianfalse
+\newif\if@arabic\@arabicfalse
+
+\DeclareOption{landscape}{
+    \@landscapetrue
+}
+\DeclareOption{russian}{
+    \@russiantrue
+}
+\DeclareOption{arabic}{
+    \@arabictrue
+}
+\ProcessOptions\relax
+
+
+% -- Setup margins --
+%
+% Tex defines to large margins for our purposes. 
+% So we redefine this to use paper more efficiently
+%
+
+\ifcase\@ptsize % 10 pt
+\hoffset=-26.5mm
+\voffset=-35mm
+\textheight=245mm
+\textwidth=175mm
+\or % 11 pt
+\hoffset=-25mm
+\voffset=-35mm
+\setlength{\textheight}{250mm}
+\setlength{\textwidth}{175mm}
+\or % 12 pt
+\hoffset=-20mm
+\voffset=-35mm
+\textheight=245mm
+\textwidth=175mm
+\fi
+
+\newlength{\thelinewidth}
+\thelinewidth=\textwidth
+
+\if@twocolumn
+\hoffset=-14.3mm
+\voffset=-38mm
+\textheight=255mm
+\textwidth=188mm
+
+\thelinewidth=0.47\textwidth
+\fi
+
+% -- End of setup margins --
+
+%---------- From package "lastpage" ------------------
+\def\lastpage@putlabel{\addtocounter{page}{-1}%
+   \immediate\write\@auxout{\string\newlabel{LastPage}{{}{\thepage}}}%
+   \addtocounter{page}{1}}
+\AtEndDocument{\clearpage\lastpage@putlabel}%
+%---------- end of "lastpage" ------------------
+
+% -- Setup sizes --
+\newlength{\exmpwidinf}
+\newlength{\exmpwidouf}
+\newlength{\exmpwidewid}
+
+\exmpwidinf=0.43\thelinewidth
+\exmpwidouf=0.43\thelinewidth
+\exmpwidewid=0.9\thelinewidth
+
+\newlength{\afterproblemhead}
+\newlength{\afterconstraints}
+\afterproblemhead=3mm
+\afterconstraints=2mm
+
+\newcommand{\problemheadfont}{\LARGE}
+\newcommand{\problemsectionfont}{\Large}
+\newcommand{\problemend}{\clearpage}
+\newcommand{\problemtextfont}{\normalsize}
+\newcommand{\beforeproblemsectioncaption}{\smallbreak\smallskip}
+\newcommand{\afterproblemsectioncaption}{\smallskip}
+
+\if@twocolumn
+    \afterproblemhead=1mm
+    \afterconstraints=1mm
+    \renewcommand{\problemheadfont}{\large}
+    \renewcommand{\problemsectionfont}{\normalsize}
+    \renewcommand{\problemend}{\par\medskip}
+    \renewcommand{\problemtextfont}{\footnotesize}
+    \renewcommand{\beforeproblemsectioncaption}{\smallbreak\smallskip}
+    \renewcommand{\afterproblemsectioncaption}{}
+\fi
+
+\if@landscape
+    \exmpwidinf=15cm
+\fi
+
+\if@russian\else
+\parindent=0mm
+\parskip=1ex
+\fi
+
+% -- End of setup sizes --
+
+% -- Setup keywords --
+
+\if@russian
+\def\kw@Problem{Задача}
+\def\kw@InputFileName{Имя входного файла:}
+\def\kw@OutputFileName{Имя выходного файла:}
+\def\kw@TimeLimit{Ограничение по времени:}
+\def\kw@MemoryLimit{Ограничение по памяти:}
+\def\kw@stdin{стандартный поток ввода}
+\def\kw@stdout{стандартный поток вывода}
+\def\kw@Input{Формат входного файла}
+\def\kw@Output{Формат выходного файла}
+\def\kw@Example{Пример}
+\def\kw@Examples{Примеры}
+\def\kw@page{Страница}
+\def\kw@of{из}
+\else
+\def\kw@Problem{Problem}
+\def\kw@InputFileName{Input file:}
+\def\kw@OutputFileName{Output file:}
+\def\kw@TimeLimit{Time limit:}
+\def\kw@MemoryLimit{Memory limit:}
+\def\kw@stdin{standard input}
+\def\kw@stdout{standard output}
+\def\kw@Input{Input}
+\def\kw@Output{Output}
+\def\kw@Example{Example}
+\def\kw@Examples{Examples}
+\def\kw@page{Page}
+\def\kw@of{of}
+\fi
+
+% -- End of setup keywords --
+
+
+% -- Problem sections --
+
+\newcommand{\createsection}{\@newsection}
+
+\def\@newsection#1#2{\DeclareRobustCommand{#1}{
+{\beforeproblemsectioncaption\noindent\bf\problemsectionfont
+\textsf{#2}}
+\nopagebreak\par\afterproblemsectioncaption}
+}
+
+\createsection{\InputFile}{\kw@Input}
+\createsection{\OutputFile}{\kw@Output}
+\createsection{\Example}{\kw@Example}
+\createsection{\Examples}{\kw@Examples}
+
+% -- End of problem sections
+
+% -- Default limits --
+
+\if@russian
+\def\defaultmemorylimit{64 мегабайта}
+\else
+\def\defaultmemorylimit{64 megabytes}
+\fi
+
+% -- End of default limits --
+
+% -- Problem environment --
+
+\newcounter{problem}
+
+\newenvironment{problem}[5]{
+
+% -- Default memory limit --
+% :FIXME:
+\def\@t{#5}
+
+\ifx\@t\empty
+    \def\@memorylimit{\defaultmemorylimit}
+\else
+\ifcat\par\@t
+    \def\@memorylimit{\defaultmemorylimit}
+\else
+    \def\@memorylimit{#5}
+\fi
+\fi
+% -- End of default memory limit --
+
+{\noindent\refstepcounter{problem}\textbf{\problemheadfont\textsf{#1}}
+\nopagebreak\par\vspace{\afterproblemhead}
+\problemtextfont\parindent=6.5mm
+\vbox{
+    \begin{tabular}{l@{\extracolsep{1cm}}l}
+    \kw@InputFileName & \texttt{#2} \\
+    \kw@OutputFileName & \texttt{#3} \\
+    \kw@TimeLimit & #4 \\
+    \kw@MemoryLimit & \@memorylimit \\
+    \end{tabular}
+}
+\nopagebreak\par\vspace{\afterconstraints}\problemtextfont}
+
+\newcommand{\InputFileName}{#2}
+\newcommand{\OutputFileName}{#3}
+}
+{\problemend}
+
+\def\s@tm@cr@s{%
+\def\widthin##1{\exmpwidinf=##1\relax}\def\widthout##1{\exmpwidouf=##1\relax}%
+\def\stretchin##1{\advance\exmpwidinf by ##1\relax}%
+\def\stretchout##1{\advance\exmpwidouf by ##1\relax}%
+}%
+
+% :FIXME:
+\newenvironment{example}[1][]{
+\s@tm@cr@s#1\ttfamily\obeylines\obeyspaces\frenchspacing%
+\newcommand{\exmp}[2]{
+\begin{minipage}[t]{\exmpwidinf}\rightskip=0pt plus 1fill\relax##1\medskip\end{minipage}&
+\begin{minipage}[t]{\exmpwidouf}\rightskip=0pt plus 1fill\relax##2\medskip\end{minipage}\\
+\hline}
+
+\begin{tabular}{|l|l|}
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\InputFileName}}&%
+\multicolumn{1}{|c|}{\bf\texttt{\OutputFileName}}\\%
+\hline
+}
+{\end{tabular}}
+
+\newenvironment{examplewide}[1][]{%
+\s@tm@cr@s#1\ttfamily\obeylines\obeyspaces\frenchspacing%
+\newcommand{\exmp}[2]{%
+\begin{tabular}{|c|}
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\InputFileName}}\\%
+\hline
+\begin{minipage}[t]{\exmpwidewid}\rightskip=0pt plus 1fill\relax
+##1
+\medskip\end{minipage}\\%
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\OutputFileName}}\\%
+\hline
+\begin{minipage}[t]{\exmpwidewid}\rightskip=0pt plus 1fill\relax
+##2    
+\medskip\end{minipage}\\%
+\hline
+\end{tabular}
+}
+}{}
+
+% -- End of problem environment --
+
+
+% -- Declare "shortitems" environment: it's a "compact itemize" --
+\def\shortitems{\vspace{-3mmplus2mm}\itemize\itemsep-1.618mmplus0.5mm\relax}%
+\def\endshortitems{\vspace{-3mmplus2mm}\enditemize}%
+% -- end of shortitems declaration --
+
+\newcommand{\thecontestname}{Olympiad in Informatics}
+\newcommand{\thecontestlocation}{Somewhere}
+\newcommand{\thecontestdate}{Once upon a time}
+
+\DeclareRobustCommand{\contestname}{\thecontestname\par\thecontestlocation\unskip, \thecontestdate}
+
+\DeclareRobustCommand{\contest}[3]{
+\renewcommand{\thecontestname}{#1}
+\renewcommand{\thecontestlocation}{#2}
+\renewcommand{\thecontestdate}{#3}
+}
+
+\makeatletter
+
+\renewcommand{\@oddhead}{%
+\parbox{\textwidth}{%
+\sffamily\begin{center}
+\protect\contestname%
+\\[2pt]
+\hrule%
+\end{center}}%
+}
+
+\renewcommand{\@oddfoot}{%
+\parbox{\textwidth}{%
+\hrule%
+\vspace{6pt}%
+\sffamily{{\hfil}\kw@page\ \thepage\ \kw@of\ \pageref{LastPage}\hfil}}%
+}%
+
+\makeatother
+ 
+\setlength{\headheight}{2cm}
+\setlength{\headsep}{6mm}
+
+\hfuzz=0.5pt
+
+\sloppy

cg2012.1/15-segment_set_intersection/statement/segment_set_intersection.tex

+\begin{problem}{15. Пересечение множества отрезков}{standard input}{standard output}{2 секунды}{256 мегабайт}
+
+На плоскости задано множество отрезков. Требуется найти все точки пересечения.
+При наложении считать только экстремальные точки этого наложения.
+Каждую точку нужно задать отрезками проходящими через нее.
+\InputFile
+В первой строке задано целое число $n$ -- количество отрезков.
+Следующие $n$ строк содержат по 4 вещественных числа — координаты начала и конца $i$-го отрезка.
+
+\OutputFile
+В первую строку выведите число $m$ -- количество точек пересечения отрезков.
+В следующие $m$ строчек выведите количество отрезков образующих $i$-ую точки пересечения и номера отрезков этих отреков. Отрезки нумеруются с единицы в порядке появления в исходных данных.  
+\Examples
+
+\begin{example}%
+\exmp{
+4
+4.0 4.0 11.0 11.0
+1.0 9.0 15.0 9.0
+6.0 12.0 14.0 4.0
+2.0 12.0 2.0 3.0
+}{
+2
+9.0 9.0 1 2 3
+2.0 9.0 2 4
+}%
+\end{example}
+
+\end{problem}

cg2012.1/15-segment_set_intersection/statement/statement.pdf

Binary file added.

cg2012.1/15-segment_set_intersection/statement/statement.tex

+\documentclass[11pt,a4paper,oneside]{article}
+
+\usepackage[T2A]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[english,russian]{babel}
+\usepackage[russian]{olymp}
+\usepackage{graphics}
+\usepackage{wrapfig}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{epigraph}
+\usepackage{lastpage}
+
+\contest{
+Вычислительная геометрия
+}{
+НИУ ИТМО
+}{
+2011/2012 учебный год
+}    
+
+\binoppenalty=10000
+\relpenalty=10000
+\exhyphenpenalty=10000
+
+\renewcommand{\t}{\texttt}
+
+\createsection{\Note}{Примечание}
+
+\renewcommand{\defaultmemorylimit}{256 мегабайт}
+
+
+\begin{document}
+
+\input segment_set_intersection.tex
+
+\end{document}

cg2012.1/15-segment_set_intersection/testgen/TestGen15.java

+import java.io.FileNotFoundException;
+import java.io.PrintWriter;
+import java.util.Random;
+
+public class TestGen15 {
+     public static void main(String[] args) throws FileNotFoundException {
+        generate(0, 50);
+        generate(1, 1);
+    }
+
+    private static void generate(int task, int count) throws FileNotFoundException {
+        PrintWriter pw;
+        String fileName, stringFormat;
+        int n, m;
+        Random random = new Random();
+
+        if (task == 0) {
+            fileName = "correctness_tests/";
+            stringFormat = "%02d";
+            //n = random.nextInt(50) + 1;
+        } else {
+            fileName = "performance_tests/";
+            n = 400000;
+            stringFormat = "%03d";
+        }
+
+        for (int i = 0; i < count; i++) {
+            String s = fileName + String.format(stringFormat, i + 1) + ".in";
+            pw = new PrintWriter(s);
+
+            if(task == 0){
+                write(pw, random.nextInt(50) + 1);
+            } else {
+                write(pw, 400000);
+            }
+        }
+    }
+    static void write(PrintWriter out, int n){
+        Random random = new Random();
+
+        out.println(n);
+        for(int i = 0; i < n; i++){
+            for(int j = 0; j < 4; j++){
+                out.print(random.nextDouble() * (1 + random.nextInt(1000)) + " ");
+            }
+            out.println();
+        }
+        out.close();
+    }
+}

cg2012.1/15-segment_set_intersection/testgen/correctness_tests/readme

+Этот файл нужен только потому, что mercurial не умеет отслеживать пустые папки, создать папку на плюсах просто только с помощью буста.

cg2012.1/15-segment_set_intersection/testgen/performance_tests/readme

+Этот файл нужен только потому, что mercurial не умеет отслеживать пустые папки, создать папку на плюсах просто только с помощью буста.

cg2012.1/22-point_shortest_path/statement/example.pdf

Binary file added.

cg2012.1/22-point_shortest_path/statement/olymp.sty

+%
+% Macros for the contest problems
+% for MikTeX: use latex.exe
+% (C) Dmitry S. Lomov (SPb SU Training Centre), 2001-2002
+% (C) Kitten Computing [Andrew Lopatin & Nick Durov], 2001-2002,2003
+% (C) Andrew Stankevich (SPb IFMO Training Center), 2003,2004
+%
+%
+% This is work in progress, please do not try to modify it.
+% 
+% Visit http://neerc.ifmo.ru/develop/olymp-sty/index.html for
+% project details.
+%
+
+\ProvidesPackage{olymp}
+
+
+\newif\if@landscape\@landscapefalse
+\newif\if@russian\@russianfalse
+\newif\if@arabic\@arabicfalse
+
+\DeclareOption{landscape}{
+    \@landscapetrue
+}
+\DeclareOption{russian}{
+    \@russiantrue
+}
+\DeclareOption{arabic}{
+    \@arabictrue
+}
+\ProcessOptions\relax
+
+
+% -- Setup margins --
+%
+% Tex defines to large margins for our purposes. 
+% So we redefine this to use paper more efficiently
+%
+
+\ifcase\@ptsize % 10 pt
+\hoffset=-26.5mm
+\voffset=-35mm
+\textheight=245mm
+\textwidth=175mm
+\or % 11 pt
+\hoffset=-25mm
+\voffset=-35mm
+\setlength{\textheight}{250mm}
+\setlength{\textwidth}{175mm}
+\or % 12 pt
+\hoffset=-20mm
+\voffset=-35mm
+\textheight=245mm
+\textwidth=175mm
+\fi
+
+\newlength{\thelinewidth}
+\thelinewidth=\textwidth
+
+\if@twocolumn
+\hoffset=-14.3mm
+\voffset=-38mm
+\textheight=255mm
+\textwidth=188mm
+
+\thelinewidth=0.47\textwidth
+\fi
+
+% -- End of setup margins --
+
+%---------- From package "lastpage" ------------------
+\def\lastpage@putlabel{\addtocounter{page}{-1}%
+   \immediate\write\@auxout{\string\newlabel{LastPage}{{}{\thepage}}}%
+   \addtocounter{page}{1}}
+\AtEndDocument{\clearpage\lastpage@putlabel}%
+%---------- end of "lastpage" ------------------
+
+% -- Setup sizes --
+\newlength{\exmpwidinf}
+\newlength{\exmpwidouf}
+\newlength{\exmpwidewid}
+
+\exmpwidinf=0.43\thelinewidth
+\exmpwidouf=0.43\thelinewidth
+\exmpwidewid=0.9\thelinewidth
+
+\newlength{\afterproblemhead}
+\newlength{\afterconstraints}
+\afterproblemhead=3mm
+\afterconstraints=2mm
+
+\newcommand{\problemheadfont}{\LARGE}
+\newcommand{\problemsectionfont}{\Large}
+\newcommand{\problemend}{\clearpage}
+\newcommand{\problemtextfont}{\normalsize}
+\newcommand{\beforeproblemsectioncaption}{\smallbreak\smallskip}
+\newcommand{\afterproblemsectioncaption}{\smallskip}
+
+\if@twocolumn
+    \afterproblemhead=1mm
+    \afterconstraints=1mm
+    \renewcommand{\problemheadfont}{\large}
+    \renewcommand{\problemsectionfont}{\normalsize}
+    \renewcommand{\problemend}{\par\medskip}
+    \renewcommand{\problemtextfont}{\footnotesize}
+    \renewcommand{\beforeproblemsectioncaption}{\smallbreak\smallskip}
+    \renewcommand{\afterproblemsectioncaption}{}
+\fi
+
+\if@landscape
+    \exmpwidinf=15cm
+\fi
+
+\if@russian\else
+\parindent=0mm
+\parskip=1ex
+\fi
+
+% -- End of setup sizes --
+
+% -- Setup keywords --
+
+\if@russian
+\def\kw@Problem{Задача}
+\def\kw@InputFileName{Имя входного файла:}
+\def\kw@OutputFileName{Имя выходного файла:}
+\def\kw@TimeLimit{Ограничение по времени:}
+\def\kw@MemoryLimit{Ограничение по памяти:}
+\def\kw@stdin{стандартный поток ввода}
+\def\kw@stdout{стандартный поток вывода}
+\def\kw@Input{Формат входного файла}
+\def\kw@Output{Формат выходного файла}
+\def\kw@Example{Пример}
+\def\kw@Examples{Примеры}
+\def\kw@page{Страница}
+\def\kw@of{из}
+\else
+\def\kw@Problem{Problem}
+\def\kw@InputFileName{Input file:}
+\def\kw@OutputFileName{Output file:}
+\def\kw@TimeLimit{Time limit:}
+\def\kw@MemoryLimit{Memory limit:}
+\def\kw@stdin{standard input}
+\def\kw@stdout{standard output}
+\def\kw@Input{Input}
+\def\kw@Output{Output}
+\def\kw@Example{Example}
+\def\kw@Examples{Examples}
+\def\kw@page{Page}
+\def\kw@of{of}
+\fi
+
+% -- End of setup keywords --
+
+
+% -- Problem sections --
+
+\newcommand{\createsection}{\@newsection}
+
+\def\@newsection#1#2{\DeclareRobustCommand{#1}{
+{\beforeproblemsectioncaption\noindent\bf\problemsectionfont
+\textsf{#2}}
+\nopagebreak\par\afterproblemsectioncaption}
+}
+
+\createsection{\InputFile}{\kw@Input}
+\createsection{\OutputFile}{\kw@Output}
+\createsection{\Example}{\kw@Example}
+\createsection{\Examples}{\kw@Examples}
+
+% -- End of problem sections
+
+% -- Default limits --
+
+\if@russian
+\def\defaultmemorylimit{64 мегабайта}
+\else
+\def\defaultmemorylimit{64 megabytes}
+\fi
+
+% -- End of default limits --
+
+% -- Problem environment --
+
+\newcounter{problem}
+
+\newenvironment{problem}[5]{
+
+% -- Default memory limit --
+% :FIXME:
+\def\@t{#5}
+
+\ifx\@t\empty
+    \def\@memorylimit{\defaultmemorylimit}
+\else
+\ifcat\par\@t
+    \def\@memorylimit{\defaultmemorylimit}
+\else
+    \def\@memorylimit{#5}
+\fi
+\fi
+% -- End of default memory limit --
+
+{\noindent\refstepcounter{problem}\textbf{\problemheadfont\textsf{#1}}
+\nopagebreak\par\vspace{\afterproblemhead}
+\problemtextfont\parindent=6.5mm
+\vbox{
+    \begin{tabular}{l@{\extracolsep{1cm}}l}
+    \kw@InputFileName & \texttt{#2} \\
+    \kw@OutputFileName & \texttt{#3} \\
+    \kw@TimeLimit & #4 \\
+    \kw@MemoryLimit & \@memorylimit \\
+    \end{tabular}
+}
+\nopagebreak\par\vspace{\afterconstraints}\problemtextfont}
+
+\newcommand{\InputFileName}{#2}
+\newcommand{\OutputFileName}{#3}
+}
+{\problemend}
+
+\def\s@tm@cr@s{%
+\def\widthin##1{\exmpwidinf=##1\relax}\def\widthout##1{\exmpwidouf=##1\relax}%
+\def\stretchin##1{\advance\exmpwidinf by ##1\relax}%
+\def\stretchout##1{\advance\exmpwidouf by ##1\relax}%
+}%
+
+% :FIXME:
+\newenvironment{example}[1][]{
+\s@tm@cr@s#1\ttfamily\obeylines\obeyspaces\frenchspacing%
+\newcommand{\exmp}[2]{
+\begin{minipage}[t]{\exmpwidinf}\rightskip=0pt plus 1fill\relax##1\medskip\end{minipage}&
+\begin{minipage}[t]{\exmpwidouf}\rightskip=0pt plus 1fill\relax##2\medskip\end{minipage}\\
+\hline}
+
+\begin{tabular}{|l|l|}
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\InputFileName}}&%
+\multicolumn{1}{|c|}{\bf\texttt{\OutputFileName}}\\%
+\hline
+}
+{\end{tabular}}
+
+\newenvironment{examplewide}[1][]{%
+\s@tm@cr@s#1\ttfamily\obeylines\obeyspaces\frenchspacing%
+\newcommand{\exmp}[2]{%
+\begin{tabular}{|c|}
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\InputFileName}}\\%
+\hline
+\begin{minipage}[t]{\exmpwidewid}\rightskip=0pt plus 1fill\relax
+##1
+\medskip\end{minipage}\\%
+\hline
+\multicolumn{1}{|c|}{\bf\texttt{\OutputFileName}}\\%
+\hline
+\begin{minipage}[t]{\exmpwidewid}\rightskip=0pt plus 1fill\relax
+##2    
+\medskip\end{minipage}\\%
+\hline
+\end{tabular}
+}
+}{}
+
+% -- End of problem environment --
+
+
+% -- Declare "shortitems" environment: it's a "compact itemize" --
+\def\shortitems{\vspace{-3mmplus2mm}\itemize\itemsep-1.618mmplus0.5mm\relax}%
+\def\endshortitems{\vspace{-3mmplus2mm}\enditemize}%
+% -- end of shortitems declaration --
+
+\newcommand{\thecontestname}{Olympiad in Informatics}
+\newcommand{\thecontestlocation}{Somewhere}
+\newcommand{\thecontestdate}{Once upon a time}
+
+\DeclareRobustCommand{\contestname}{\thecontestname\par\thecontestlocation\unskip, \thecontestdate}
+
+\DeclareRobustCommand{\contest}[3]{
+\renewcommand{\thecontestname}{#1}
+\renewcommand{\thecontestlocation}{#2}
+\renewcommand{\thecontestdate}{#3}
+}
+
+\makeatletter
+
+\renewcommand{\@oddhead}{%
+\parbox{\textwidth}{%
+\sffamily\begin{center}
+\protect\contestname%
+\\[2pt]
+\hrule%
+\end{center}}%
+}
+
+\renewcommand{\@oddfoot}{%
+\parbox{\textwidth}{%
+\hrule%
+\vspace{6pt}%
+\sffamily{{\hfil}\kw@page\ \thepage\ \kw@of\ \pageref{LastPage}\hfil}}%
+}%
+
+\makeatother
+ 
+\setlength{\headheight}{2cm}
+\setlength{\headsep}{6mm}
+
+\hfuzz=0.5pt
+
+\sloppy

cg2012.1/22-point_shortest_path/statement/point_shortest_path.tex

+\begin{problem}{22. Кратчайший путь материальной точки между точками плоскости с полигональными препятствиями}{standard input}{standard output}{2 секунды}{256 мегабайт}
+
+На плоскости заданы две точки: начальное и конечное положение робота. Также на плоскости заданы полигональные препятствия.
+Робот должен добраться из начальной точки в конечную по кратчайшему пути, при этом он может касаться препятствий.
+Кратчайший путь нужно задать точками, где робот меняет направление своего движения. Существование пути гарантируется.
+  
+\InputFile
+В первой строке заданы координаты старта и финиша соответственно.
+Во второй строке задано количество препятствий $n$.
+Далее следует $n$ блоков, задающих препятствия.
+В первой строке каждого блока записано количество вершин $m$ в препятствии. В следующих $m$ строках заданы координаты вершин препятствия.
+
+\OutputFile
+
+В первой строке выходного файла выведите количество поворотов, сделанных роботом -- $k$.
+В следующие $k$ строчек выведите координаты точек пути, где робот соверщал поворот. Точки выводятся в порядке обхода. 
+Если кратчайших путей несколько, выведите любой из них.
+\Examples
+
+\begin{example}%
+\exmp{
+0.0 0.0 25.0 17.0
+2
+3
+3.0 6.0
+7.0 3.0
+10.0 8.0
+3
+21.0 7.0    
+20.0 14.0
+14.0 12.0
+}{
+2 
+7.0 3.0 
+14.0 12.0 
+}%
+\end{example}
+
+\Note
+Пояснение к примеру:
+\begin{center}
+	\includegraphics{example.pdf}
+\end{center}
+\end{problem}

cg2012.1/22-point_shortest_path/statement/statement.pdf

Binary file added.

cg2012.1/22-point_shortest_path/statement/statement.tex

+\documentclass[11pt,a4paper,oneside]{article}
+
+\usepackage[T2A]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[english,russian]{babel}
+\usepackage[russian]{olymp}
+\usepackage{graphics}
+\usepackage{wrapfig}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{epigraph}
+\usepackage{lastpage}
+
+\contest{
+Вычислительная геометрия
+}{
+НИУ ИТМО
+}{
+2011/2012 учебный год
+}    
+
+\binoppenalty=10000
+\relpenalty=10000
+\exhyphenpenalty=10000
+
+\renewcommand{\t}{\texttt}
+
+\renewcommand{\defaultmemorylimit}{256 мегабайт}
+
+\createsection{\Note}{Примечание}
+
+\begin{document}
+
+\input point_shortest_path.tex
+
+\end{document}