poj1039--Pipe（計算幾何）

poj1039--Pipe（計算幾何）

題目大意：一條管子有n個折點，給出管子上壁n個點的坐標(x1,y1)(x2,y2)....，x1

如果想讓光照的最遠，那麼除了全程的可能外，光一定會與某一個管壁相交，並且會與管中的兩個節點相交，否則就可以調整光的角度，使其照的更遠，枚舉這兩個點的位置，然後逐個點處判斷相交的位置。

#include 
#include 
#include 
#include 
using namespace std ;
#define eqs 1e-9
/*
兩直線相交，求焦點
ax + by + c = 0 ;
ux + vy + w = 0 ;
a/u != b/v 防止平行
交點:( (b*w-v*c)/(a*v-u*b) , (c*u-a*w)/(a*v-u*b) )
*/
struct point
{
    double x , y ;
} p[30];
int n ;
double a[4][4] = { {0,0,0,0},{0,-1,0,0},{0,0,0,-1},{0,-1,0,-1} } ;
double solve(point u,point v) {
    double a = (u.y-v.y)/(u.x-v.x) , b = u.y-a*u.x ;
    double x , y , ans = 0.0 ;
    int flag = 0 , i ;
    y = a*p[0].x + b ;
    if( y-p[0].y >= eqs || p[0].y-1.0-y >= eqs  ) return ans ;
    for(i = 1 ; i < n ; i++) {
        y = a*p[i].x + b ;
        if( y-p[i].y > eqs ) {
            flag = 1 ;
            break ;
        }
        else if( p[i].y-1.0-y > eqs ) {
            flag = 2 ;
            break ;
        }
        else
            ans += (p[i].x-p[i-1].x) ;
    }
    if( !flag ) return ans ;
    u = p[i-1] , v = p[i] ;
    if( flag == 2 ) u.y -= 1.0 , v.y -= 1.0 ;
    double k = (u.y-v.y)/(u.x-v.x) , c = u.y-k*u.x ;
    x = (b-c)/(k-a) ;
    ans += (x-p[i-1].x) ;
    return ans ;
}
int main()
{
    int  i , j , k ;
    double max1 , temp ;
    point u , v ;
    while( scanf(%d, &n) && n )
    {
        max1 = 0.0 ;
        for(i = 0 ; i < n ; i++)
            scanf(%lf %lf, &p[i].x, &p[i].y) ;
        for(i = 0 ; i < n ; i++)
            for(j = i+1 ; j < n ; j++)
                for(k = 0 ; k < 4 ; k++) {
                    u.x = p[i].x + a[k][0] ; u.y = p[i].y + a[k][1] ;
                    v.x = p[j].x + a[k][2] ; v.y = p[j].y + a[k][3] ;
                    temp = solve(u,v) ;
                    if( temp > max1 )
                        max1 = temp ;
                }
        if( fabs(p[n-1].x-p[0].x-max1) < eqs  )
            printf(Through all the pipe.
) ;
        else
            printf(%.2lf
, p[0].x+max1) ;
    }
    return 0 ;
}