先介绍几种极角排序：
1.利用叉积的正负来作cmp.(即是按逆时针排序).此题就是用这种方法
1
bool
cmp(
const
point &a,
const
point &b)
//
逆时针排序
2
{
3
point origin;
4
origin.x = origin.y =
0
;
5
return
cross(origin,b,origin,a) <
0
;
6
}
2.利用complex的内建函数。
1
#include<complex>
2
#define
x real()
3
#define
y imag()
4
#include<algorithm>
5
using
namespace
std;
6
7
bool
cmp(
const
Point& p1,
const
Point& p2)
8
{
9
return
arg(p1) < arg(p2);
10
}
3.利用arctan计算极角大小。（范围『-180，180』）
1
bool
cmp(
const
Point& p1,
const
Point& p2)
2
{
3
return
atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
4
}
4.利用象限加上极角，叉积。
1
bool
cmp(
const
point &a,
const
point &b)
//
先按象限排序，再按极角排序，再按远近排序
2
{
3
if
(a.y ==
0
&& b.y ==
0
&& a.x*b.x <=
0
)
return
a.x>b.x;
4
if
(a.y ==
0
&& a.x >=
0
&& b.y !=
0
)
return
true
;
5
if
(b.y ==
0
&& b.x >=
0
&& a.y !=
0
)
return
false
;
6
if
(b.y*a.y <=
0
)
return
a.y>b.y;
7
point one;
8
one.y = one.x =
0
;
9
return
cross(one,a,one,b) >
0
|| (cross(one,a,one,b) ==
0
&& a.x < b.x);
10
}
好了，差不多了。
顺便推荐个网站： http://www.csie.ntnu.edu.tw/~u91029/PointLinePlane2.html （上面讲的很详细）
这题的数据应该只有一组：
View Code
1
#include<iostream>
2
#include<cmath>
3
#include<complex>
4
#include<algorithm>
5
#define
max(a,b) (a)>(b)?(a):(b)
6
#define
min(a,b) (a)<(b)?(a):(b)
7
#define
EPS 1e-8
8
using
namespace
std;
9
struct
point {
10
double
x,y;
11
};
12
point convex[
50
];
13
14
double
cross(
const
point &p1,
const
point &p2,
const
point &q1,
const
point &q2)
15
{
16
return
(q2.y - q1.y)*(p2.x - p1.x) - (q2.x - q1.x)*(p2.y - p1.y);
17
}
18
19
bool
cmp(
const
point &a,
const
point &b)
20
{
21
point origin;
22
origin.x = origin.y =
0
;
23
return
cross(origin,b,origin,a) <
0
;
24
}
25
26
27
int
main()
28
{
29
int
cnt =
0
;
30
while
(scanf(
"
%lf%lf
"
,&convex[cnt].x,&convex[cnt].y) != EOF) {
31
++cnt;
32
}
33
sort(convex+
1
,convex+cnt,cmp);
34
for
(
int
i(
0
); i<cnt; ++i) {
35
cout<<
"
(
"
<<convex[i].x<<
"
,
"
<<convex[i].y<<
"
)
"
<<endl;
36
}
37
return
0
;
38
}
