PKU1039 Pipe 计算几何线段交点

模板：给定L1上两点（ax,ay），（bx,by），L2上两点（cx,cy），（dx,dy），求两直线交点（x,y）。

double cross( double x1, double y1, double x2, double y2){ return x1 * y2 - x2 * y1;} void intersec(point a, point b, point c, point d, double * x, double * y){ double u = cross(d.x - a.x, d.y - a.y, b.x - a.x, b.y - a.y); double v = cross(c.x - a.x, c.y - a.y, b.x - a.x, b.y - a.y); double w = u - v; * x = (u * 1.0 * c.x - v * 1.0 * d.x) / (w * 1.0 ); * y = (u * 1.0 * c.y - v * 1.0 * d.y) / (w * 1.0 );}  1039Accepted200K63MS

63MS是有些慢，这一题是刘汝佳的《算法艺术与信息学竞赛》P359的例题。

思路：枚举上下两个顶点成光线所在直线，然后判断光线是否合法，合法的话枚举判断光线与管道上下壁是否相交，并存下最远的交点横坐标。

代码 #include < iostream > #include < cmath > using namespace std; #define MAXN 25 #define eps 1e-8 struct point{ double x,y; point( double xx = 0 , double yy = 0 ){ x = xx; y = yy; } point operator - ( const point & a) const { return point(x - a.x, y - a.y); } double operator * ( const point & a) const { // 叉积 return x * a.y - y * a.x; } void input() { scanf( " %lf%lf " , & x, & y); }}upper[MAXN],botto[MAXN]; int n; int sgn( double x){ return (x > eps) - (x <- eps);} void intersec(point a, point b, point c, point d, double * x, double * y){ double u = (d - a) * (b - a); double v = (c - a) * (b - a); double w = u - v; * x = (u * c.x - v * d.x) / w; * y = (u * c.y - v * d.y) / w;} // 判断直线L（a,b）和线段L（up,down）是否相交 bool check(point a,point b,point up,point down){ double tx,ty; intersec(a,b,up,down, & tx, & ty); if (sgn(ty - up.y) <= 0 && sgn(ty - down.y) >= 0 ) return true ; return false ;} void slove(){ int i,j,k,flag; double maxx,tx,ty; maxx = upper[ 1 ].x; // 初始化 for (i = 1 ;i <= n;i ++ ) { for (j = 1 ;j <= n;j ++ ) { flag = 0 ; if (i == j) continue ; for (k = (i > j ? i:j);k >= 0 ;k -- ) { if (check(upper[i],botto[j],upper[k],botto[k]) == 0 ) break ; } if (k >= 1 ) continue ; for (k = 1 ;k <= n;k ++ ) { if (check(upper[i],botto[j],upper[k],botto[k]) == 0 ) break ; } if (k > n) { flag = 1 ; break ;} intersec(upper[i],botto[j],upper[k - 1 ],upper[k], & tx, & ty); if (sgn(tx - upper[k - 1 ].x) >= 0 && sgn(tx - upper[k].x) <= 0 ) if (maxx < tx) maxx = tx; intersec(upper[i],botto[j],botto[k - 1 ],botto[k], & tx, & ty); if (sgn(tx - botto[k - 1 ].x) >= 0 && sgn(tx - botto[k].x) <= 0 ) if (maxx < tx) maxx = tx; } if (flag) break ; } if (flag) puts( " Through all the pipe. " ); else printf( " %.2lf\n " ,maxx);} int main(){ while (scanf( " %d " , & n),n) { for ( int i = 1 ;i <= n;i ++ ) { upper[i].input(); botto[i].x = upper[i].x; botto[i].y = upper[i].y - 1 ; } slove(); } return 0 ;}

 

转载于:https://www.cnblogs.com/DreamUp/archive/2010/09/03/1817109.html

相关资源：JAVA上百实例源码以及开源项目