极角是极坐标系中的角度
我们对这个角度进行点的排序
利用类的概念设置结构体
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 101001; const LL INF = 0x3f3f3f3f3f3f3f3f; int n; class Point{ public: LL x, y; int xiang; ///象限 public: Point(LL a = 0, LL b = 0) { x = a, y = b; if(x >= 0 && y >= 0) xiang = 1; else if(x >= 0 && y <= 0) xiang = 4; else if(x <= 0 && y >= 0) xiang = 2; else xiang = 3; } void judge(){//调整象限 if(x >= 0 && y >= 0) xiang = 1; else if(x >= 0 && y <= 0) xiang = 4; else if(x <= 0 && y >= 0) xiang = 2; else xiang = 3; } Point operator-(Point a){ return Point(x-a.x, y-a.y); } Point operator+(Point a){ return Point(x+a.x, y+a.y); } }p[N], np[N];///np 存储的是真正的极角 LL Cross(Point a, Point b){ return a.x * b.y - a.y * b.x; } bool cmp(Point a, Point b){///真真正正的排序 if(a.xiang == b.xiang)//再按照叉积 return Cross(a, b) > 0; else ///先按照象限 return a.xiang < b.xiang; } bool cmp2(Point a, Point b){///只是按照叉积排序 return Cross(a, b) > 0; } void Show(){ cout<<"\n\n"; for(int i = 0; i < n; i++){ printf("%d %lld %lld\n", p[i].xiang, p[i].x, p[i].y); } } int main(){ cin>>n; for(int i = 0; i < n; i++){ cin>>p[i].x>>p[i].y; p[i].judge(); } sort(p, p + n, cmp); ///极点排序 Show(); return 0; }
原文链接: https://www.cnblogs.com/lucky-light/p/12972856.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/351212
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!