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 代码过不去样例,才发现排序锅了)