本文主要是介绍POJ 1039 Pipe，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
枚举任意两个点作为直线。
看是否能穿越整个管道即可。
判断相交使用叉积。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 211111
#define eps 1e-8
#define INF 50000001
using namespace std;
inline int dblcmp(double d)
{if(fabs(d) < eps) return 0;return d > eps ? 1 : -1;
}
struct point
{double x, y;point(){}point(double _x, double _y): x(_x), y(_y) {}void input(){scanf("%lf%lf", &x, &y);}bool operator ==(point a)const{return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;}point sub(point p){return point(x - p.x, y - p.y);}double dot(point p){return x * p.x + y * p.y;}double det(point p){return x * p.y - y * p.x;}double distance(point p){return hypot(x - p.x, y - p.y);}
}a[25], b[25];
struct line
{point a, b;line(){}line(point _a, point _b){ a = _a; b = _b;}void input(){a.input();b.input();}int segcrossseg(line v){int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));int d3 = dblcmp(v.b.sub(v.a).det(a.sub(v.a)));int d4 = dblcmp(v.b.sub(v.a).det(b.sub(v.a)));if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;return (d1 == 0 && dblcmp(v.a.sub(a).dot(v.a.sub(b))) <= 0||d2 == 0 && dblcmp(v.b.sub(a).dot(v.b.sub(b))) <= 0||d3 == 0 && dblcmp(a.sub(v.a).dot(a.sub(v.b))) <= 0||d4 == 0 && dblcmp(b.sub(v.a).dot(b.sub(v.b))) <= 0);}int linecrossseg(line v)//v is seg{int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));if ((d1 ^ d2) == -2) return 2;return (d1 == 0 || d2 == 0);}point crosspoint(line v){double a1 = v.b.sub(v.a).det(a.sub(v.a));double a2 = v.b.sub(v.a).det(b.sub(v.a));return point((a.x * a2 - b.x * a1) / (a2 - a1), (a.y * a2 - b.y * a1) / (a2 - a1));}};
int n;
double ans;
int gao(line x, int id)
{int ind = -1;int kind = -1;for(int i = 0; i < n - 1; i ++){if(dblcmp(x.b.sub(x.a).det(a[i].sub(x.a))) < 0 || dblcmp(x.b.sub(x.a).det(a[i + 1].sub(x.a))) < 0){ind = i;kind = 1;break;}if(dblcmp(x.b.sub(x.a).det(b[i].sub(x.a))) > 0 || dblcmp(x.b.sub(x.a).det(b[i + 1].sub(x.a))) > 0){ind = i;kind = 2;break;}}if(ind != -1 && ind < id) return 0;if(ind == -1) return 1;line y;if(kind == 1) y = line(a[ind], a[ind + 1]);else y = line(b[ind], b[ind + 1]);point c = x.crosspoint(y);ans = max(ans, c.x);return 0;
}
int main()
{while(scanf("%d", &n) != EOF && n){for(int i = 0; i < n; i++){a[i].input();b[i].x = a[i].x;b[i].y = a[i].y - 1;}ans = a[0].x;int flag = 0;for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++){line x = line(a[i], b[j]);flag |= gao(x, j);x = line(b[i], a[j]);flag |= gao(x, j);if(flag) break;}if(flag) puts("Through all the pipe.");else printf("%.2f\n", ans);}return 0;
}这篇关于POJ 1039 Pipe的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
