/*
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) 编辑 收藏 引用