Graham算法求解P3829(luogu)信用卡时WA,求调。

Question

用Graham算法求凸包，luogu上pts90(WA in #8,12);
球调帖
评测记录
code

#include<bits/stdc++.h>
using namespace std;
struct node{
    double x,y;
    double angle;
    node operator-(const node p)const{
         return{x-p.x,y-p.y,0};
    }
}p[40001];
int n;
double l,h,r;
double x,y,th;
int s1[40001];
double ju(node x,node y){
    return sqrt((x.y-y.y)*(x.y-y.y)+(y.x-x.x)*(y.x-x.x));
}
bool cmp(node x,node y){
    if(x.angle==y.angle){
        return ju(x,p[1])>ju(y,p[1]);
    }
    return x.angle>y.angle;
}
double jiao(node x,node y){
    return x.x*y.y-x.y*y.x;
}
void init(){
    int tot=0;
    cin>>n;
    cin>>l>>h>>r;
    for(int i=1;i<=n;i++){
//        cout<<"i"<<i<<endl;
        cin>>x>>y>>th;
//        cout<<"i"<<i<<endl;
        p[++tot].x=(h/2-r)*cos(th)-(l/2-r)*sin(th)+x;
        p[tot].y=(l/2-r)*cos(th)+(h/2-r)*sin(th)+y;
        p[++tot].x=-(h/2-r)*cos(th)-(l/2-r)*sin(th)+x;
        p[tot].y=(l/2-r)*cos(th)-(h/2-r)*sin(th)+y;
        p[++tot].x=(h/2-r)*cos(th)+(l/2-r)*sin(th)+x;
        p[tot].y=-(l/2-r)*cos(th)+(h/2-r)*sin(th)+y;
        p[++tot].x=-(h/2-r)*cos(th)+(l/2-r)*sin(th)+x;
        p[tot].y=-(l/2-r)*cos(th)-(h/2-r)*sin(th)+y;
    }
    n=tot;
}
node st[400001];
int top;
int main(){
    init();
    int k,xx,yy;
    for(int i=1;i<=n;i++){
        if(i==1){
            k=i;
            xx=p[i].x;
            yy=p[i].y;
        }
        if(p[i].x<xx||(p[i].x==xx&&p[i].y<yy)){
            k=i;
            xx=p[i].x;
            yy=p[i].y;
        }
    }
    swap(p[k],p[1]);
    for(int i=1;i<=n;i++){
        p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y);
    }
    sort(p+2,p+n+1,cmp);
    st[++top]=p[1];
    for(int i=2;i<=n;i++){
        while(top>=2&&
          jiao(st[top]-st[top-1],p[i]-st[top])<=0){
            top--;
        }
        st[++top]=p[i];
    }
    st[top+1]=p[1];
    double ans=0;
    for(int i=1;i<=top;i++){
        ans+=ju(st[i],st[i+1]);
//        cout<<st[i].x<<" "<<st[i].y<<endl;
    }
    if(r!=0){
        printf("%.2lf",ans+double(3.141592653589793)*(double)2*r);
        return 0;
    }
    printf("%.2lf",ans);
}

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

你的代码中存在一些问题，特别是在计算点的坐标和处理凸包的算法细节上。以下是一些可能的改进措施：

1. 修正角度计算：p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y); 这里应该是 p[i].angle = atan2(p[i].y - p[1].y, p[i].x - p[1].x);。

2. 修正向量叉积计算：jiao(st[top]-st[top-1],p[i]-st[top])<=0 这里的计算应该确保正确地表示方向。

3. 修正凸包构建：确保在构建凸包时没有遗漏或错误的判断条件。

以下是修改后的代码：

#include <bits/stdc++.h>
using namespace std;

struct node {
    double x, y;
    double angle;
    node operator-(const node &p) const {
        return {x - p.x, y - p.y};
    }
};

node p[40001];
int n;

double l, h, r;
double x, y, th;
int s1[40001];

double ju(const node &x, const node &y) {
    return sqrt((x.y - y.y) * (x.y - y.y) + (x.x - y.x) * (x.x - y.x));
}

bool cmp(const node &x, const node &y) {
    if (fabs(x.angle - y.angle) < 1e-9) {
        return ju(x, p[1]) > ju(y, p[1]);
    }
    return x.angle < y.angle;
}

double jiao(const node &x, const node &y) {
    return x.x * y.y - x.y * y.x;
}

void init() {
    int tot = 0;
    cin >> n >> l >> h >> r;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y >> th;
        p[++tot].x = (h / 2 - r) * cos(th) - (l / 2 - r) * sin(th) + x;
        p[tot].y = (l / 2 - r) * cos(th) + (h / 2 - r) * sin(th) + y;
        p[++tot].x = -(h / 2 - r) * cos(th) - (l / 2 - r) * sin(th) + x;
        p[tot].y = (l / 2 - r) * cos(th) - (h / 2 - r) * sin(th) + y;
        p[++tot].x = (h / 2 - r) * cos(th) + (l / 2 - r) * sin(th) + x;
        p[tot].y = -(l / 2 - r) * cos(th) + (h / 2 - r) * sin(th) + y;
        p[++tot].x = -(h / 2 - r) * cos(th) + (l / 2 - r) * sin(th) + x;
        p[tot].y = -(l / 2 - r) * cos(th) - (h / 2 - r) * sin(th) + y;
    }
    n = tot;
}

node st[400001];
int top;

int main() {
    init();
    int k, xx, yy;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || p[i].y < yy || (p[i].y == yy && p[i].x < xx)) {
            k = i;
            xx = p[i].x;
            yy = p[i].y;
        }
    }
    swap(p[k], p[1]);
    for (int i = 1; i <= n; i++) {
        p[i].angle = atan2(p[i].y - p[1].y, p[i].x - p[1].x);
    }
    sort(p + 2, p + n + 1, cmp);
    st[++top] = p[1];
    for (int i = 2; i <= n; i++) {
        while (top >= 2 && jiao(st[top] - st[top - 1], p[i] - st[top]) <= 0) {
            top--;
        }
        st[++top] = p[i];
    }
    st[top + 1] = p[1];
    double ans = 0;
    for (int i = 1; i <= top; i++) {
        ans += ju(st[i], st[i + 1]);
    }
    if (r != 0) {
        printf("%.2f\n", ans + 2 * M_PI * r);
    } else {
        printf("%.2f\n", ans);
    }
    return 0;
}

关键修改点：

1. 角度计算修正：p[i].angle = atan2(p[i].y - p[1].y, p[i].x - p[1].x);
2. 排序比较函数：if (fabs(x.angle - y.angle) < 1e-9) 用于处理浮点数精度问题。
3. 凸包构建逻辑：确保在构建凸包时没有遗漏或错误的判断条件。

希望这些修改能帮助你通过评测。如果还有问题，请继续反馈。