POJ 1039 Pipe 题解

这题属实阴间，明明20内的数据，第三层循环不剪枝会t，%.2lf输出会WA，ans必须从-Infinity开始更新。

题目大意：给你一条曲折的管道，管道y向宽度永远为1，你可以在管道入口射一束光，求这束光最远能射到的x坐标。注意光不会被反射，会被管壁所阻挡。但管子端点如果在光前进路线上则不算挡住光。管道数<=20（？）

善用Geogebra

题目本身的英文描述写的真的读的我一头雾水= =因为数据范围不算大（？）题目入手方向还是枚举线段的端点，拿一条直线来暴力检验。

思路：最优的一条光线只有可能是与某两条管道中的两个端点相交的直线。因为如果不是，则平移这条直线则会得到一个更优的解。

细节：n^2枚举管子的线段，不能只从入口的两个端点去算解，因为最优光线不一定经过入口的端点。注意管子端点的处理，如果只是仅仅忽略端点则有可能光线穿出管子导致未预期的解，如图。

具体实现：将题目所给的管子端点构造出描述整个管子的线段对象。

枚举：双层枚举这些线段，用前一维的from与后一维的to构造一个待验证光线（直线对象）

检验：枚举线段，用直线去与线段所在直线求交点，如果交点在线段内，判断是不是在端点上。并且为了不让光线穿出管道，我们要分类讨论上下管道壁。对于上壁，当且仅当交点为from且管壁的斜率小于光线斜率的时候会被阻挡，对于下壁，管壁斜率大于光线斜率时光线会被阻挡。