xfstart07
Get busy living or get busy dying

/*
PROG: fence3
LANG: C++
*/

#include
< iostream >
#include
< cmath >
using   namespace  std;

typedef 
struct {
    
int  x,y;
}Point;
int  N;
Point a[
151 ][ 2 ];
double  ans,ax,ay;
void  swap(Point x,Point y){
    Point tmp
= x;
    x
= y;
    y
= tmp;
}
void  init()
{
    scanf(
" %d " , & N);
    
for ( int  i = 1 ;i <= N; ++ i){
        scanf(
" %d%d%d%d " , & a[i][ 0 ].x, & a[i][ 0 ].y, & a[i][ 1 ].x, & a[i][ 1 ].y);
        
if (a[i][ 0 ].x > a[i][ 1 ].x || a[i][ 0 ].y > a[i][ 1 ].y)
            swap(a[i][
0 ],a[i][ 1 ]);
    }
}
inline 
double  sqr( double  x){
    
return  x * x;
}
inline 
double  min( double  x, double  y){
    
if (x > y)  return  y;
    
return  x;
}
double  dist( double  x, double  y){   // 计算点到线的距离
     double  dis = 0 ;
    
for ( int  i = 1 ;i <= N; ++ i)
        
if (a[i][ 0 ].x < x && a[i][ 1 ].x > x)   // 在x轴上
            dis += abs(y - a[i][ 0 ].y);
        
else   if (a[i][ 0 ].y < y && a[i][ 1 ].y > y)   // 在y轴上
            dis += abs(x - a[i][ 0 ].x);
        
else  dis += min(sqrt(sqr(x - a[i][ 0 ].x) + sqr(y - a[i][ 0 ].y)),
                              sqrt(sqr(x
- a[i][ 1 ].x) + sqr(y - a[i][ 1 ].y)));   // 找两端的最小值
     return  dis;
}
void  solve()
{
    
double  d = 10 ;   // 精度
     double  dx = 0 ,dy = 0 ;
    ans
= 0xFFFFFFF ;
    
do {
        
for ( int  i = 0 ;i <= 10 ; ++ i)
            
for ( int  j = 0 ;j <= 10 ; ++ j){    // 枚举点走的距离
                 double  tmp = dist(dx + d * i,dy + d * j);
                
if (tmp < ans){
                    ans
= tmp;
                    ax
= dx + d * i;
                    ay
= dy + d * j;
                }
            }
        dx
= ax - d;
        dy
= ay - d;
        d
/= 5.0 ;
    }
while (d >= 0.001 );
    printf(
" %0.1lf %0.1lf %0.1lf\n " ,ax,ay,ans);
}
int  main()
{
    freopen(
" fence3.in " , " r " ,stdin);
    freopen(
" fence3.out " , " w " ,stdout);
    init();
    solve();
    
return   0 ;
}



posted on 2009-07-16 14:07 xfstart07 阅读(113) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理