Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include < iostream >
#include < cmath >
using namespace std;

const double Inf = 1000000000;
int n;
typedef struct
{
double x, y;
}Point;
Point pipe[2][25];
double ans;
bool through;

double det(double x1, double y1, double x2, double y2)
{
return x1*y2-x2*y1;
}

double cross(Point a, Point b, Point c)
{
return (det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y));
}

int dblcmp(double t)
{
if (fabs(t) < 1e-11)
   return 0;
return t > 0 ? 1 : -1;
}

bool LineIntersect(Point p1, Point p2, Point p3, Point p4)
{
double v1 = dblcmp(cross(p1,p2,p3));
double v2 = dblcmp(cross(p1,p2,p4));
if (v1*v2 > 0)
   return false;
return true;
}

bool LineIntersect(Point p1, Point p2, Point p3, Point p4, bool)
{
double s1, s2;
s1 = cross(p1,p2,p3);
s2 = cross(p1,p2,p4);
double temp;
temp = (p3.x*s2-p4.x*s1)/(s2-s1);
if (temp > ans)
   ans = temp;
return false;
}

void solve(Point p1, Point p2, const int ri, const int rj)
{
int i;
for (i = 0; i < n; ++i) {
   if (!LineIntersect(p1, p2, pipe[0][i], pipe[1][i])) {
    break;
   }
}
if (i < rj)
   return;
if (i >= n) {
   through = true;
   return;
}
if (i > rj) {
   LineIntersect(p1, p2, pipe[0][i-1], pipe[0][i],1);
   LineIntersect(p1, p2, pipe[1][i-1], pipe[1][i],1);
   return;
}
}

int main()
{
while (scanf("%d", &n), n) {
   int i;
   for (i = 0; i < n; ++i) {
    scanf("%lf %lf", &pipe[0][i].x, &pipe[0][i].y);
    pipe[1][i].x = pipe[0][i].x;
    pipe[1][i].y = pipe[0][i].y-1;
   }
 
   ans = -Inf;
   through = false;
   for(i = 0; i < n; ++i)
    for (int k = 0; k < 2; ++k)
     for (int j = i + 1; j < n; ++j) {
      if (!through) {
       solve(pipe[k][i],pipe[1-k][j],i, j);
      }
      else
       break;
     }
 
   if (through) {
    printf("Through all the pipe.\n");
   }
   else
    printf("%.2lf\n", ans);
}
return 0;
}