POJ 1113
这道题是凸包第一题，也是我学习算法的一题。直接看了题解，看别人怎么写的然后自己模仿，写出自己的凸包模板
这道题，直接凸包然后算个长度就可以了
#include <iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; struct point { int x,y,dx,dy; point():x(0),y(0),dx(0),dy(0) {} void getdxdy(int x0,int y0) { dx=x-x0,dy=y-y0; } bool mlut(point p1, point p2) { return ( (p1.x-x)*(p2.y-p1.y)>(p2.x-p1.x)*(p1.y-y)); } bool operator < (const point & p)const { return ( dx*p.dy>dy*p.dx||( p.dx*dy==dx*p.dy && dy<p.dy ) ); } }; point pnt[1310],ac[1310]; int tb(point p[] ,int n) { int k=0; for(int i=1;i<n;i++) { if(p[i].y<p[k].y || (p[i].y==p[k].y &&p[i].x<p[i].y) ) k=i; } if(k>0) { point t=p[0]; p[0]=p[k]; p[k]=t ;} for(int i=0;i<n;i++) { p[i].getdxdy(p[0].x,p[0].y); } sort(p+1,p+n); if(n==0) return 0; ac[0]=p[0]; if(n==1) return 1; ac[1]=p[1]; if(n==2) return 2; ac[2]=p[2]; int top=2; for(int i=3;i<n;i++) { while( top>=1 && !ac[top-1].mlut(ac[top],p[i]) ) top--; ac[++top]=p[i]; } return top+1; } double c(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double cc(int n,int l) { double ans=0; for(int i=1;i<n;++i) { ans+=c(ac[i],ac[i-1]); } if(n!=2) ans+=c(ac[n-1],ac[0]); ans+=2*3.141592653*l; return ans; } int main() { int n,l; while(scanf("%d%d",&n,&l)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d",&pnt[i].x,&pnt[i].y); int top=tb(pnt,n); printf("%d\n",(int)(cc(top,l)+0.5) ); } return 0; } 然后自己做了一道题，发现自己其实还是没太掌握黑上模板，结果这道题只是一个简单的叉积排序就ok了，还是自己太弱，对代码不够熟悉 #include <iostream> #include<cmath> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const double eps = 1e-8; struct point { double x,y; }; int dblcmp(double k) { if (fabs(k) < eps) return 0; return k > 0 ? 1 : -1; } point pnt[1005]; double multi(point p0, point p1, point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } bool cmp(const point& a, const point& b) { return dblcmp(multi(pnt[0], a, b)) > 0; } int n; int main() { int n = 0, i; while (scanf ("%lf%lf", &pnt[n].x, &pnt[n].y) != EOF) n++; sort(pnt+1, pnt+n, cmp); for (i = 0; i < n; i++) printf ("(%.0lf,%.0lf)\n", pnt[i].x, pnt[i].y); return 0; }
