先介紹幾種極角排序：
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
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
