import java.io.*; import java.util.*; public class Main { Scanner in; PrintWriter out; String FILE_NAME = "exam"; double INF = 1e100; double EPS = 1e-6; // Координаты ворот double[] x; double[][] y; // Пусть мы едем по прямой, соединяющей точки // (x[f],y[f][f1]) и (x[l],y[l][l1]) // Тогда процедура возвращает, проезжаем ли мы внутри ворот // с номером n или нет public boolean good(int f, int f1, int l, int l1, int n){ double yy = cou(f,f1,l,l1,n); return (yy<=y[n][1]+EPS && yy>=y[n][0]-EPS); } // Пусть мы едем по прямой, соединяющей точки // (x[f],y[f][f1]) и (x[l],x[l][l1]) // Тогда процедура возвращает координату по y, в которой // наш путь пересечёт прямую x = x[n] public double cou(int f, int f1, int l, int l1, int n){ double dx = x[l]-x[f]; double dy = y[l][l1]-y[f][f1]; double yy = (x[n]-x[f])/dx*dy+y[f][f1]; return yy; } // Проверяет, проедем ли мы все ворота от номера b по номер a, // если будем двигаться по прямой (x[f],y[f][f1]) и (x[l],x[l][l1]) // При этом неважно, пройдём ли мы через остальные ворота public boolean tr(int f, int f1, int l, int l1, int b, int a){ for(int i=b;i<=a;i++){ if (!good(f,f1,l,l1,i)){ return false; } } return true; } // Возвращает угол поворота, если мы ехали от точки (x[i],y[i][i1]) до точки // (x[j],y[j][j1]), а в ней повернули на точку (x[k],x[k][k1) public double ang(int i, int i1, int j, int j1, int k, int k1){ double a = (x[k]-x[j])*(x[j]-x[i])+(y[k][k1]-y[j][j1])*(y[j][j1]-y[i][i1]); a/=Math.sqrt((x[k]-x[j])*(x[k]-x[j])+(y[k][k1]-y[j][j1])*(y[k][k1]-y[j][j1])); a/=Math.sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j][j1]-y[i][i1])*(y[j][j1]-y[i][i1])); a = Math.min(a,1); a = Math.max(a,-1); return Math.acos(a); } public void run() throws Exception{ Locale.setDefault(Locale.US); in = new Scanner(new File(FILE_NAME+".in")); out= new PrintWriter(new FileWriter(new File(FILE_NAME+".out"))); // количество ворот int n = in.nextInt(); x = new double[n]; y = new double[n][2]; for(int i=0;iy[i][1]){ double t = y[i][0]; y[i][0] = y[i][1]; y[i][1] = t; } } // may[f][f1][l][l1] говорит, можем ли мы ехать по прямой от // точки (x[f],y[f][f1]) до точки (x[l],y[l][l1]) // mayb содержит почти то же самое, однако он говорит, могли ли // мы по этой ехать по этой прямой с самого начала до точки (x[l],e[l][l1]) // а mayf - могли ли мы ехать по ней до конца. boolean[][][][] may = new boolean[n][2][n][2]; boolean[][][][] mayb =new boolean[n][2][n][2]; boolean[][][][] mayf =new boolean[n][2][n][2]; for(int i=0;ip){ best = p; bi = i; bj = j; bi1 = i1; bj1 = j1; } } } out.println(best); //Восстановление ответа double[] r = new double[n]; for(int i=bi;i