題意：幾何計算，給出一個管道（一條從左到右的折線，與它向下移動1后的折線構成），問管道最左邊發出的光線所能到達的最遠位置的橫坐標是多少。

分析：容易知道，要求一個能到達最遠的光線，這條光線一定是經過至少兩個折線的折點（每個這點可能是上面折線的，也可能是下面折線的），那么我們就每次枚舉兩個管道折點，求一直線看該直線與管道邊緣線段交點。在求的過程中，可以從左到右依次判斷是否與各個折點的橫斷面相交，然后可以得知是否會與管道壁相交。通過直線在橫斷面對應橫坐標的位置的縱坐標高于還是低于橫斷面?？梢耘袛嗥渑c那個管道壁相交，求交點即可。然后在所有交點中找一個橫坐標最小的。

View Code #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
usingnamespace std;

#define maxn 25
#define eps 1.0e-8

struct Point
{
double x, y;
} point[maxn];

int n;
double ans;
bool ok;

void input()
{
for (int i =0; i < n; i++)
scanf("%lf%lf", &point[i].x, &point[i].y);
}

double intersect(Point a1, Point b1, Point a2, Point b2)
{
double x1 = a1.x, x2 = b1.x, x3 = a2.x, x4 = b2.x;
double y1 = a1.y, y2 = b1.y, y3 = a2.y, y4 = b2.y;
double x =(y3-y1+x1*(y2-y1)/(x2-x1)-x3*(y4-y3)/(x4-x3))/((y2-y1)/(x2-x1)-(y4-y3)/(x4-x3));
return x;
}

void work(Point a, Point b)
{
b.y -=1;
for (int i =0; i < n; i++)
{
Point p, q1, q2;
p.x = point[i].x;
p.y = a.y - (b.y - a.y) / (b.x - a.x) * (a.x - p.x);
if ((p.y + eps < point[i].y && p.y - eps > point[i].y -1) || abs(p.y
- point[i].y) < eps || abs(p.y - point[i].y +1) < eps)
continue;
if (i ==0)
return;
if (p.y - eps > point[i].y)
ans = max(ans, intersect(a, b, point[i -1], point[i]));
else
{
q1 = point[i -1];
q1.y -=1;
q2 = point[i];
q2.y -=1;
ans = max(ans, intersect(a, b, q1, q2));
}
return;
}
ok =true;
}

int main()
{
//freopen("t.txt", "r", stdin);
while (scanf("%d", &n), n)
{
input();
ans = point[0].x;
ok =false;
for (int i =0; i < n; i++)
for (int j =0; j < n; j++)
if (i != j &&!ok)
work(point[i], point[j]);
if (ok)
printf("Through all the pipe.\n");
else
printf("%.2f\n", ans);
}
return0;
}

轉載于:https://www.cnblogs.com/rainydays/archive/2011/07/03/2096818.html

總結

以上是生活随笔為你收集整理的poj1039的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。