3059. 极坐标排序

10175101245

对于角度大小的比较,最简单的想法肯定是算出来再比。
但是反三角函数计算可能有误差存在,导致本题神坑数据无法AC……
虽然这题我是用python写的,但实际上不是因为python浮点数运算精度高。
于是我用了比较古老的方法比较角的大小:先按象限比,同一象限再比正切值……
递归调用一次只是为了省略部分代码……
当然,输出角的大小还是得用反三角~

import math

def ang_cmp(x1, y1, x2, y2): #比较两个复数辐角大小的封装函数,当且仅当前一对坐标对应辐角更小时返回True
    if y1 < 0 and y2 >= 0: #三四象限的角一定比一二象限大
        return False
    elif y2 < 0 and y1 >= 0: #同理
        return True
    elif y1 >= 0 and y2 >= 0: #同在一二象限
        if (x1 < 0 and x2 < 0) or (x1 >= 0 and x2 >= 0): #在同一象限
            return y1 * x2 < y2 * x1 #正切值的比较,用乘法避免除以0的尴尬
        else: #此情况下必为一角在(pi/2,pi]内,另一角在[0,pi/2]内,只需判断前面一对是不是落在第一象限(及坐标轴)的那个
            return x1 >= 0 
    else: #同在三四象限:只需反转到一二象限,交换一下比较顺序即可
        return ang_cmp(x2, -y2, x1, -y1)


class vec: #封装需要排序的复数类
    def __init__(self, x, y): 
        self.rel = x
        self.img = y
        z = complex(x, y)
        self.r = float(abs(z)) #计算模长,复数的abs就是模长
        if y >= 0:
            self.angle = float(math.acos(x/self.r))
        else:
            self.angle = float(math.pi * 2 - math.acos(x/self.r))

    def __lt__(self, other): #python定义类的大小比较的函数,当且仅当self < other时返回True
        x1, y1 = self.rel, self.img
        x2, y2 = other.rel, other.img
        if  ang_cmp(x1, y1, x2, y2) or ang_cmp(x2, y2, x1, y1): #两次小于判断相当于不等于的判断
            return ang_cmp(x1, y1, x2, y2)
        else:
            return self.r > other.r

    def __str__(self): #定义类与字符串的转换
        s = '(%.4f,%.4f)' % (self.r, self.angle)
        return s

# main

q = int(input())
for t in range(q):
    print("case #%d:" % t)
    n = int(input())
    ls = list()
    for i in range(n):
        a, b = map(float, input().split())
        ls.append(vec(a, b))
    ls.sort()
    for i in range(n):
        print(ls[i])
Li Dao

这个挺牛批的,至少比我当年写的垃圾代码好多了

Li Dao

为什么过不去呢?
浮点数有误差
要这样比较abs(aa.sita-bb.sita)>ESP
ESP是个常量
这里设置为const double ESP=10e-6;

Li Dao

这我还能说什么,有毒
我还能说什么,精度从10^-3-10^-9枚举了一遍,只有10^-8是对的

include

using namespace std;

struct dian
{
double x,y;
double l,sita;
dian(double x=0,double y=0,double l=0,double sita=0)
{
this->x=x;
this->y=y;
this->l=l;
this->sita=sita;
};
};

const double mypi=3.14159265358979323846;
const double ESP=10e-8;
vector mylist;

int mycmp(dian aa,dian bb)
{
if(abs(aa.sita-bb.sita)>ESP) return aa.sita-bb.sita<0;
else return aa.l-bb.l>0;
}
void qcal()
{
for(int i=0;i<mylist.size();i++)
{
double xx=mylist[i].x,yy=mylist[i].y;
mylist[i].l=sqrt(xxxx+yyyy);
double si=atan2(yy,xx);
if(si<0) si+=2*mypi;
mylist[i].sita=si;
}
return;
}

int main()
{
int T;
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
int n;
mylist.clear();
scanf(“%d”,&n);
for(int i=1;i<=n;i++)
{
double xx,yy;
scanf(“%lf%lf”,&xx,&yy);
mylist.push_back(dian(xx,yy,0,0));
}
qcal();
sort(&mylist[0],&mylist[n],mycmp);
printf(“case #%d:\n”,step);
for(int i=0;i<n;i++)
printf(“(%0.4lf,%0.4lf)\n”,mylist[i].l,mylist[i].sita);
}
return 0;
}

改个名字吧
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct Ans{
    double p,o;
};

int cmp(const Ans&a,const Ans&b)
{
    if(abs(a.o-b.o)<=10e-8)
        return a.p>b.p;
    else return a.o<b.o;
}
int main()
{
    int T;
    cin>>T;
    for(int i=0;i<T;i++)
    {
        int N;
        cin>>N;
        Ans ans[N];
        for(int ii=0;ii<N;ii++)
        {
            double x,y;
            cin>>x>>y;
            ans[ii].p=sqrt(x*x+y*y);
            if(y>=0) ans[ii].o=acos(x/ans[ii].p);
            else ans[ii].o=2*acos(-1)-acos(x/ans[ii].p);
        }   

        sort(ans,ans+N,cmp);
        printf("case #%d:\n",i);
        for(int ii=0;ii<N;ii++)
            printf("(%.4lf,%.4lf)\n",ans[ii].p,ans[ii].o);
    }
}```
Saitama

有毒啊,,

改个名字吧

include

include

include

include

using namespace std;
struct Ans{
double p,o;
};

int cmp(const Ans&a,const Ans&b)
{
if(abs(a.o-b.o)<=10e-8)
return a.p>b.p;
else return a.o>T;
for(int i=0;i>N;
Ans ans[N];
for(int ii=0;ii>x>>y;
ans[ii].p=sqrt(xx+yy);
if(y>=0) ans[ii].o=acos(x/ans[ii].p);
else ans[ii].o=2*acos(-1)-acos(x/ans[ii].p);
}

    sort(ans,ans+N,cmp);
    printf("case #%d:\n",i);
    for(int ii=0;ii<N;ii++)
        printf("(%.4lf,%.4lf)\n",ans[ii].p,ans[ii].o);
}

}

改个名字吧

删不掉。。。打扰了 (原来贴代码的时候用三个```把代码包起来就可以完整显示了哇

Deuchie

看前面说好像有坑?不过我似乎无意间避开了 Orz

struct RadCoor {
    double rho, theta; // double ρ, θ;
};

struct RecCoor {
    double x, y;
    RadCoor to_rad() const {
        return { std::sqrt(x * x + y * y), x == 0 && y == 0 ? 0 : [&]() {
            constexpr double pi = 3.14159265359;
            auto a = atan2(y, x);
            return a < 0 ? a + 2 * pi : a;
        }() };
    }
};

int main() {
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t n; cin >> n;
        vector<RecCoor> recs(n);
        for (auto& point : recs) {
            cin >> point.x >> point.y;
        }
        vector<RadCoor> rads(n);
        transform(recs.begin(), recs.end(), rads.begin(), [](auto const& point) {return point.to_rad(); });
        sort(rads.begin(), rads.end(), [](auto const& a, auto const& b) {
            if (a.theta == b.theta) {
                return a.rho > b.rho;
            } else {
                return a.theta < b.theta;
            }
        });
        for (auto const& point : rads) {
            printf("(%.4lf,%.4lf)\n", point.rho, point.theta);
        }
    }
}
你当前正在回复 博客/题目
存在问题!