http://acm.nyist.net/JudgeOnline/problem.php?pid=142
第一道解析几何问题，比较纠结，主要是几个解析几何的基本操作，包括求两线段的叉积，判断左右方向，判断是否相交， 计算交点等等，主要的思路就是穷举所有的折点的组合，取任意两个折点组成一条线，看看能不能跟所有的管道的上下折点构成的线段相交，如果所有都相交则说明光线能通过，否则求出所有光线中照的最远的那个（穷举的过程中设置一个记录变量） 这里就需要计算两个线段的交点（如果不能穿过管道，就要计算管道壁和光线的交点）。
#include<stdio.h>
#include<math.h>
struct point
{
double x, y;
};
double det(double x1, double y1, double x2, double y2) //计算叉积
{
return x1 * y2 - x2 * y1;
}
double cross(point a, point b, point p) //判断左右方向
{
return det(b.x - a.x, b.y - a.y, p.x - a.x, p.y - a.y);
}
double check(point a1, point a2, point b1, point b2) //判断是否相交
{
return cross(a1, a2, b1) * cross(a1, a2, b2);
}
double getarea(point a, point b, point c)
{
double ab = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
double ac = sqrt((a.x - c.x) * (a.x - c.x) + (a.y - c.y) * (a.y - c.y));
double bc = sqrt((c.x - b.x) * (c.x - b.x) + (c.y - b.y) * (c.y - b.y));
double q = (ab + ac + bc) / 2;
return sqrt(q * (q - ab) * (q - ac) * (q - bc));
}
double calculate(point a1, point a2, point b1, point b2)//计算x坐标值
{
double s1 = getarea(a1, a2, b1);
double s2 = getarea(a1, a2, b2);
return (s1 * b2.x + s2 * b1.x) / (s1 + s2);
}
int main()
{
int n;
while(scanf("%d", &n), n != 0)
{
int i;
point pip[25][2];
for(i = 0; i < n; i++)
{
scanf("%lf %lf", &pip[i][0].x, &pip[i][0].y);
pip[i][1].x = pip[i][0].x;
pip[i][1].y = pip[i][0].y - 1;
}
int j;
double max_x = -0x7fffffff;
bool flag = false;
point a, b;
for(i = 0; i < n && flag == false; i++)
{
int index1, index2;
int temp = 0;
for(temp = 0; temp < 2; temp ++)
{
a = pip[i][temp];
for(index1 = i + 1 ; index1 < n && flag == false; index1 ++)
{
for(index2 = 0; index2 < 2 && flag == false; index2 ++)
{
b = pip[index1][index2];
if( check(a, b, pip[0][0], pip[0][1]) - 0 < 1e-6 )
{
for(j = 1; j < n; j++)
{
if( check(a, b, pip[j][0], pip[j][1]) - 0 > 1e-6)
{
double x;
if(cross(a, b, pip[j][0]) > 0)
x = calculate(a, b, pip[j - 1][1], pip[j][1]);
else
x = calculate(a, b, pip[j - 1][0], pip[j][0]);
if(x > max_x)
max_x = x;
break;
}
}
if(j == n)
flag = true;
}
}
}
}
}
if(flag == true)
printf("Through all the pipe.\n");
else
printf("%.2lf\n", max_x);
}
return 0;
}