/*
PROG: fc
LANG: C++
*/
#include
<
iostream
>
#include
<
cmath
>
#include
<
cstdlib
>
using
namespace
std;
typedef
struct
{
double
x,y;
}Point;
int
N,top;
Point P[
10001
],
*
stack[
10001
],ST;
double
FP(Point
&
l1s,Point
&
l1e,Point
&
l2s,Point
&
l2e)
{
Point l1,l2;
l1.x
=
l1e.x
-
l1s.x; l1.y
=
l1e.y
-
l1s.y;
l2.x
=
l2e.x
-
l2s.x; l2.y
=
l2e.y
-
l2s.y;
return
l1.x
*
l2.y
-
l2.x
*
l1.y;
}
inline
double
dis(
double
x1,
double
y1,
double
x2,
double
y2)
{
return
sqrt((x1
-
x2)
*
(x1
-
x2)
+
(y1
-
y2)
*
(y1
-
y2));
}
int
cmp(
const
void
*
A,
const
void
*
B){
Point
*
a
=
(Point
*
)A,
*
b
=
(Point
*
)B;
double
fp
=
FP(
*
a,ST,
*
b,ST);
if
(fp
<
0
)
return
1
;
if
(fp
==
0
&&
dis(a
->
x,a
->
y,ST.x,ST.y)
<
dis(b
->
x,b
->
y,ST.x,ST.y))
return
1
;
return
-
1
;
}
void
init()
{
scanf(
"
%d
"
,
&
N);
double
max1
=-
0xFFFFFFF
;
int
st;
for
(
int
i
=
1
;i
<=
N;
++
i){
scanf(
"
%lf%lf
"
,
&
P[i].x,
&
P[i].y);
if
(P[i].x
>
max1){
max1
=
P[i].x;
ST
=
P[i];
st
=
i;
}
}
P[st]
=
P[N]; N
--
;
qsort(P
+
1
,N,
sizeof
(Point),cmp);
}
void
graham()
{
stack[
0
]
=&
ST;
stack[top
=
1
]
=&
P[
1
];
for
(
int
i
=
2
;i
<=
N;
++
i){
stack[
++
top]
=&
P[i];
while
(FP(
*
stack[top],
*
stack[top
-
1
],
*
stack[top
-
2
],
*
stack[top])
<
0
)
{
stack[top
-
1
]
=
stack[top];
top
--
;
}
}
}
void
out
()
{
double
res
=
0
;
for
(
int
i
=
1
;i
<=
top;
++
i)
res
+=
dis(stack[i
-
1
]
->
x,stack[i
-
1
]
->
y,stack[i]
->
x,stack[i]
->
y);
res
+=
dis(stack[top]
->
x,stack[top]
->
y,stack[
0
]
->
x,stack[
0
]
->
y);
printf(
"
%0.2lf\n
"
,res);
}
int
main()
{
freopen(
"
fc.in
"
,
"
r
"
,stdin);
freopen(
"
fc.out
"
,
"
w
"
,stdout);
init();
graham();
out
();
return
0
;
}
/*
Executing
Test 1: TEST OK [0.011 secs, 3016 KB]
Test 2: TEST OK [0.000 secs, 3148 KB]
Test 3: TEST OK [0.000 secs, 3148 KB]
Test 4: TEST OK [0.000 secs, 3148 KB]
Test 5: TEST OK [0.011 secs, 3148 KB]
Test 6: TEST OK [0.022 secs, 3148 KB]
Test 7: TEST OK [0.032 secs, 3148 KB]
Test 8: TEST OK [0.043 secs, 3148 KB]
*/
posted on 2009-07-14 16:28
xfstart07 阅读(159)
评论(0) 编辑 收藏 引用