凸包，Graham扫描法模板（以洛谷P2742为例），网上的一个凸包详解相关博客：https://blog.csdn.net/ZCY19990813/article/details/98034495
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 100005 using namespace std; double X,Y; struct node { double x,y; }e[maxn],stk[maxn]; bool cmp(node a,node b) { if (a.y==b.y) return a.x<b.x; return a.y<b.y; } bool cmp2(node a,node b)//极角排序 { if (atan2(a.y-Y,a.x-X)==atan2(b.y-Y,b.x-X)) return a.x<b.x; return (atan2(a.y-Y,a.x-X))<(atan2(b.y-Y,b.x-X)); } double cross(node a,node b,node c) { node ab,ac; ab.x=b.x-a.x; ab.y=b.y-a.y; ac.x=c.x-a.x; ac.y=c.y-a.y; return ab.x*ac.y-ab.y*ac.x; } double getdis(node a,node b) { node ab; ab.x=b.x-a.x; ab.y=b.y-a.y; return sqrt(ab.x*ab.x+ab.y*ab.y); } int main() { int i,n,top; double ans; scanf("%d",&n); for (i=0;i<n;i++) scanf("%lf%lf",&e[i].x,&e[i].y); if (n<3) { if (n==1) printf("0 "); else if (n==2) printf("%.2lf ",getdis(e[0],e[1])); return 0; } sort(e,e+n,cmp); top=-1; stk[++top]=e[0]; X=e[0].x;Y=e[0].y; sort(e+1,e+n,cmp2); stk[++top]=e[1]; for (i=2;i<n;i++) { while (cross(stk[top-1],stk[top],e[i])<0) top--; stk[++top]=e[i]; } ans=0; for (i=1;i<=top;i++) { ans+=getdis(stk[i],stk[i-1]); } ans+=getdis(stk[0],stk[top]); printf("%.2lf ",ans); return 0; }
凸包+旋转卡壳模板题（洛谷P1452）
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 100005 #define eps 1e-8 using namespace std; double X,Y; int n,top; struct node { double x,y; }e[maxn],stk[maxn]; double cross(node a,node b,node c) { node ab,ac; ab.x=b.x-a.x; ab.y=b.y-a.y; ac.x=c.x-a.x; ac.y=c.y-a.y; return ab.x*ac.y-ab.y*ac.x; } double getdis(node a,node b) { node ab; ab.x=b.x-a.x; ab.y=b.y-a.y; return ab.x*ab.x+ab.y*ab.y; } bool cmp(node a,node b) { if (a.y==b.y) return a.x<b.x; return a.y<b.y; } bool cmp2(node a,node b)//极角排序 { if (atan2(a.y-Y,a.x-X)==atan2(b.y-Y,b.x-X)) return a.x<b.x; return (atan2(a.y-Y,a.x-X))<(atan2(b.y-Y,b.x-X)); } void graham() { int i; sort(e+1,e+n+1,cmp); top=-1; stk[++top]=e[1]; X=e[1].x;Y=e[1].y; sort(e+2,e+n+1,cmp2); for (i=2;i<=n;i++) { while (top>1 && cross(stk[top-1],stk[top],e[i])<eps) top--; stk[++top]=e[i]; } } int main() { int i,j; double dist,ans=0; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%lf%lf",&e[i].x,&e[i].y); graham(); stk[++top]=stk[0]; j=1; for (i=0;i<top;i++) { while (cross(stk[i+1],stk[j],stk[i])<cross(stk[i+1],stk[j+1],stk[i])) j=(j+1)%top; dist=getdis(stk[i],stk[j]); if (dist>ans) ans=dist; dist=getdis(stk[i+1],stk[j+1]); if (dist>ans) ans=dist; } printf("%.0lf ",ans); return 0; }
把每个点 的坐标转化为(x,y-x2)，函数转化为y-x2=bx+c。这样就把抛物线转化为了直线，原问题就变成了有多少条直线满足上方没有点。
求n个点中上凸包上的线段数量（点数-1）即可。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 100005 using namespace std; struct node { double x,y; }e[maxn],stk[maxn]; bool cmp(node a,node b) { if (a.x==b.x) return a.y<b.y; return a.x<b.x; } double cross(node a,node b,node c) { node ab,ac; ab.x=b.x-a.x; ab.y=b.y-a.y; ac.x=c.x-a.x; ac.y=c.y-a.y; return ab.x*ac.y-ab.y*ac.x; } double getdis(node a,node b) { node ab; ab.x=b.x-a.x; ab.y=b.y-a.y; return sqrt(ab.x*ab.x+ab.y*ab.y); } int main() { int i,n,top; double ans; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%lf%lf",&e[i].x,&e[i].y); e[i].y-=e[i].x*e[i].x; } sort(e+1,e+n+1,cmp); top=0; for (i=1;i<=n;i++) { while (top>1 && cross(stk[top-1],stk[top],e[i])>=0) top--; stk[++top]=e[i]; } if (stk[1].x==stk[2].x) top--; printf("%d ",top-1); return 0; }
D POJ 1259