这题数据有点水?
查看原帖
这题数据有点水?
353688
王熙文楼主2021/11/25 21:21

RT,看一下我的这个“AC”代码:

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

int n;

struct point
{
    double x,y;
    point() {}
    point(double _x,double _y) { x=_x,y=_y; }
} p[100010],st[100010];

bool cmp(point x,point y)
{
    if(x.y==p[1].y && y.y==p[1].y) return x.x<y.x;
    else if(x.y==p[1].y) return 1;
    else if(y.y==p[1].y) return 1;
    else if(x.x==p[1].x && x.x==y.x) return x.y<y.y;
    return (x.x-p[1].x)/(x.y-p[1].y)>(y.x-p[1].x)/(y.y-p[1].y);
}

bool check(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return (x2-x1)*(y3-y2)-(x3-x2)*(y2-y1)<=0;
}

double get_dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main()
{
    scanf("%d",&n);
    double in=1e9,inx;
    int wz;
    for(int i=1; i<=n; ++i)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i].y<in)
        {
            in=p[i].y;
            inx=p[i].x;
            wz=i;
        }
        else if(p[i].y==in && p[i].x<inx)
        {
            inx=p[i].x;
            wz=i;
        }
    }
    swap(p[1],p[wz]);
    sort(p+2,p+n+1,cmp);
    int cnt=0;
    st[++cnt]=point(p[1].x,p[1].y);
    for(int i=2; i<=n; ++i)
    {
        while(cnt>1 && check(st[cnt-1].x,st[cnt-1].y,st[cnt].x,st[cnt].y,p[i].x,p[i].y)) --cnt;
        st[++cnt]=point(p[i].x,p[i].y);
    }
    double ans=0;
    for(int i=1; i<=cnt; ++i)
    {
        if(i==cnt) ans+=get_dis(st[i].x,st[i].y,st[1].x,st[1].y);
        else ans+=get_dis(st[i].x,st[i].y,st[i+1].x,st[i+1].y);
    }
    printf("%.2f",ans);
    return 0;
}

单看 cmp:

bool cmp(point x,point y)
{
    if(x.y==p[1].y && y.y==p[1].y) return x.x<y.x;
    else if(x.y==p[1].y) return 1;
    else if(y.y==p[1].y) return 1; // 这里显然应该 return 0
    else if(x.x==p[1].x && x.x==y.x) return x.y<y.y;
    return (x.x-p[1].x)/(x.y-p[1].y)>(y.x-p[1].x)/(y.y-p[1].y);
}

注释部分显然应该 return 0

但是它 AC 了

hack: (其实是 CF50C 的样例转化一下)

14
0 1
1 2
2 1
1 0
4 1
5 2
6 1
5 0
4 3
5 4
6 3
0 3
1 4
2 3

ans:

17.66

我的输出:24.40

(话说我做 CF50C 的时候还奇怪呢怎么 AC 代码过不去样例,才发现排序锅了)

2021/11/25 21:21
加载中...