81. 极角排序

题目大意

思路讲解

AC代码

AC
https://qoj.ac/submission/2001485

源代码

/**
 * Problem: 极角排序
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-10259
 * Created: 2026-02-03 12:49:30
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

/*2026-2-3 增加编译器识别 Real 类型的功能，以使用不同类型的这个实现
 *
 */
using Real = ll;
int sgn(auto x) {
    if (-eps < x && x < eps) return 0;
    return x < 0 ? -1 : 1;
}
struct Point {
    Real x, y;
    ll idx;

    explicit Point(Real x_ = 0, Real y_ = 0) : x(x_), y(y_) {}

    // 只对左值生效的复合运算符
    Point &operator+=(Point p) & {
        x += p.x, y += p.y;
        return *this;
    }
    Point &operator-=(Point p) & {
        x -= p.x, y -= p.y;
        return *this;
    }
    Point &operator*=(Real t) & {
        x *= t, y *= t;
        return *this;
    }
    Point &operator/=(Real t) & {
        x /= t, y /= t;
        return *this;
    }

    Point operator-() const { return Point(-x, -y); }

    friend Point operator+(Point a, Point b) { return a += b; }
    friend Point operator-(Point a, Point b) { return a -= b; }
    friend Point operator*(Point a, Real b) { return a *= b; }
    friend Point operator*(Real a, Point b) { return b *= a; }
    friend Point operator/(Point a, Real b) { return a /= b; }

    friend bool operator<(Point a, Point b) {
        int sx = sgn(a.x - b.x);
        if (sx != 0) return a.x < b.x;
        return a.y < b.y;
    }
    friend bool operator>(Point a, Point b) { return b < a; }
    friend bool operator==(Point a, Point b) {
        return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
    }
    friend bool operator!=(Point a, Point b) { return !(a == b); }

    friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
    // friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

    Real norm() const { return x * x + y * y; }
    DB abs() const { return sqrt(norm()); }
};
using Vector = Point;
auto cross(Point a,Point b){
    // 在 Real 为整数的时候，使用 __int128_t 整型进行计算
    if constexpr (is_integral_v<Real>) {
        return (__int128_t)a.x*b.y-(__int128_t)a.y*b.x;
    }else {
        return a.x*b.y-a.y*b.x;
    }
}
// Real cross(Point p1, Point p2, Point p0) { // 叉乘 (p1 - p0) x (p2 - p0);
//     return cross(p1 - p0, p2 - p0);
// }
auto dot(Point a,Point b){
    // 在 Real 为整数的时候，使用 __int128_t 整型进行计算
    if constexpr (is_integral_v<Real>) {
        return (__int128_t)a.x*b.x+(__int128_t)a.y*b.y;
    }else {
        return a.x*b.x+a.y*b.y;
    }
}
// 采用两点式
struct Line{
    Point p1,p2;
    Line(){}
    Line(Point a,Point b):p1(a),p2(b) {}
    friend bool operator<(Line a,Line b){
        if(a.p1!=b.p1) return a.p1<b.p1;
        return a.p2<b.p2;
    }
    friend bool operator==(Line a,Line b){
        if(a.p1!=b.p1) return false;
        if(a.p2!=b.p2) return false;
        return true;
    }
    friend istream& operator>>(istream& is, Line& e) {
        Real a,b,c,d;
        is >> a >> b >> c >> d;
        e = Line(Point(a,b),Point(c,d));
        return is;
    }
    // friend ostream&operator<<(ostream &os, Line l) {
    //     return os << "<" << l.p << ", " << l.q << ">";
    // }
};
// 使用这个东西，Point 必须是 double 等小数类型
Point project(Point p,Line l){
    Point vec=l.p2-l.p1;
    //                        这个距离反正早除晚除都要除掉
    DB r = dot(vec,p-l.p1)/((DB)vec.x*vec.x+vec.y*vec.y);
    return l.p1+vec*r;
}
Point reflect(Point p,Line l){
    Point proj=project(p, l);
    return proj+proj-p;
}
mt19937 rng(233);

#define ON_SEGMENT 0
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE (-1)
#define ONLINE_BACK 2
#define ONLINE_FRONT (-2)

int CCW(Point p,Line l){
    Vector a=l.p2-l.p1,b=p-l.p1;
    if(sgn(cross(a,b))>0){
        return COUNTER_CLOCKWISE;
    }
    if(sgn(cross(a,b))<0){
        return CLOCKWISE;
    }
    if(sgn(dot(a, b))<0){
        return ONLINE_BACK;
    }
    if(a.norm()<b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool isOrthogonal(Line a,Line b){
    Vector c=a.p2-a.p1,d=b.p2-b.p1;
    return !sgn(dot(c,d));
}
bool isParallel(Line a,Line b){
    Vector c=a.p2-a.p1,d=b.p2-b.p1;
    return !sgn(cross(c,d));
}
bool isIntersect(Line a,Line b){    // 判断线段相交
    return CCW(b.p1,a)*CCW(b.p2,a)<=0 && CCW(a.p1,b)*CCW(a.p2,b)<=0;
}
// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
// Real 必须设为 DB
Point getintersect(const Line &a,const Line &b){
    Point p=a.p1, v=a.p2-a.p1,q=b.p1,w=b.p2-b.p1;
    Point u=p-q;
    DB t=cross(w,u)/cross(v,w);
    return p+v*t;
}
// 也可以用 project 来算
DB distancePL(Point p,Line l){
    auto val=cross(l.p2-l.p1,p-l.p1);
    return sgn(val)*val/(l.p2-l.p1).abs();
}
DB distancePS(Point p,Line l){
    Vector t=l.p2-l.p1;
    if(sgn(dot(t,p-l.p1))<0){
        return (p-l.p1).abs();
    }
    if(sgn(dot(t,p-l.p2))>0){
        return (p-l.p2).abs();
    }
    return distancePL(p, l);
}
DB distanceSS(Line a,Line b){
    if(isIntersect(a, b)) return 0;
    return min({distancePS(a.p1, b),distancePS(a.p2,b),distancePS(b.p1, a),distancePS(b.p2, a)});
}
DB polygonArea(const vector<Point> &poly){
    DB res=0;
    for (int i=0;i<poly.size();++i){
        res+=cross(poly[i],poly[(i+1)%SZ(poly)])/2;
    }
    res=abs(res);
    return res;
}
// 要求给出的点按照逆时针方向给出
bool isConvex(const vector<Point> &poly){
    for (int i=0;i<poly.size();++i){
        ll i1=(i+1)%SZ(poly),i2=(i+2)%SZ(poly);
        Vector a=poly[i]-poly[i1],b=poly[i2]-poly[i1];
        if(sgn(cross(a,b))>0){
            return false;
        }
    }
    return true;
}
// 2 是包含，1是在线上，0是出界
int isInPolygon(Point p,const vector<Point> &poly){
    ll res=0;
    Line l(p,p+Point(2e5,rng()));
   for (int i=0;i<poly.size();++i){
        int i1=(i+1)%SZ(poly);
        Line seg=Line(poly[i],poly[i1]);
        int ccw=CCW(p,seg);
        if(ccw==ON_SEGMENT){
            return 1;
        }
        if(isIntersect(l,seg)){
            ++res;
        }
    }
    // 奇偶法则，多边形内点的射线一定只会经过奇数条边。
    if(res&1) return 2;
    return 0;
}
// 定义获取区域的辅助函数，辅助
int get_part_of_point(const Point &p) {
    if (p.y < 0) return 0; // 下半平面 (-pi, 0)
    if (p.y == 0 && p.x >= 0) return 1; // 角度为 0 的部分 (含原点)
    return 2; // 上半平面 (0, pi]
}
// 你需要将所有点按照 atan2(yi,xi)进行排序，也即从 x 轴负半轴（不含）开始进行逆时针排序。
// AC https://qoj.ac/submission/2001485
void polar_angle_sort(vector<Point> &poly) {
    sort(poly.begin(),poly.end(),[](const Point &a,const Point &b)->bool {
        int part1=get_part_of_point(a),part2=get_part_of_point(b);
        if (part1!=part2) {
            return part1<part2;
        }
        return sgn(cross(a,b))==1;
    });
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> poly(N);
    for (int i=0;i<N;++i) {
        cin>>poly[i];
        poly[i].idx=i+1;
    }
    polar_angle_sort(poly);
    for (int i=0;i<N;++i) {
        cout<<poly[i].idx<<" ";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // cin >> lT;
    // while (lT--)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2001485

*/

心路历程（WA，TLE，MLE……）