POJ3348-凸包

题意：一片草地上有n课树，现在你想用绳子圈出一个尽可能大的面积出来养牛。已知每只牛需要50单位的面积，问最多能养几只牛。

1.按极角排序。

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int n,stack[10010],top; const int maxn = 1e6+10; const double eps = 1e-8; struct Tpoint{ double x; double y; }list[10010];; int dblcmp(double p){ if(fabs(p)<eps) return 0; return p>0?1:-1; } double dist(Tpoint a, Tpoint b){ return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } double Cross(Tpoint p0, Tpoint p1, Tpoint p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } bool cmp(Tpoint p1, Tpoint p2){ double temp = Cross(list[0],p1,p2); int tt = dblcmp(temp); if(!tt) return dist(list[0],p1) < dist (list[0],p2); return tt>0; } void Graham(){ Tpoint p0 = list[0]; int k = 0; for(int i=1;i<n;i++){ if(p0.y>list[i].y || (p0.y==list[i].y && p0.x>list[i].x)){ p0 = list[i]; k = i; } } swap(list[k], list[0]); sort(list+1, list+n, cmp); stack[0] = 0; stack[1] = 1; top = 1; for(int i=2;i<n;i++){ while( dblcmp(Cross(list[stack[top-1]], list[stack[top]],list[i])<0)){ top--; } stack[++top] = i; } } void init(){ for(int i=0 ; i < n ; i++ ) scanf("%lf%lf",&list[i].x,&list[i].y); memset(stack,0,sizeof(stack)); } void sov(){ double area = 0; for (int i = 0; i <= top; i++) area +=fabs(Cross(list[stack[(i+1)%(top+1)]],list[stack[i]],list[stack[0]])); printf ("%d\n", (int)area/100); } int main(){ while(~scanf("%d",&n)){ if(n == 1||n == 2) { printf("0\n");continue;} init(); Graham(); sov(); } }

2.按x排序。（x相同按y排序）

从小到大遍历，走到最大是一半的凸包，然后从大到小在走一遍，另半个凸包

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int n,stack[10010],top; const int maxn = 1e6+10; const double eps = 1e-8; struct Tpoint{ double x; double y; }list[10010];; int dblcmp(double p){ if(fabs(p)<eps) return 0; return p>0?1:-1; } double Cross(Tpoint p0, Tpoint p1, Tpoint p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } bool cmp(Tpoint p1, Tpoint p2){ if(p1.y == p2.y) return p1.x < p2.x; return p1.y < p2.y; } void Graham(){ top = 1; for(int i = 0 ; i <= 2; i++) stack[i] = i; for(int i=2;i<n;i++){ while(top && dblcmp(Cross(list[stack[top-1]], list[stack[top]],list[i])<0)){ top--; } stack[++top] = i; } int len = top; stack[++top] = n-2; for(int i = n-3; i >= 0 ; i--){ while(top!=len && dblcmp(Cross(list[stack[top-1]], list[stack[top]],list[i])<0)) top--; stack[++top] = i; } } void init(){ for(int i=0 ; i < n ; i++ ) scanf("%lf%lf",&list[i].x,&list[i].y); memset(stack,0,sizeof(stack)); sort(list, list+n, cmp); } void sov(){ double area = 0; for (int i = 0; i <= top; i++) area +=fabs(Cross(list[stack[(i+1)%(top+1)]],list[stack[i]],list[stack[0]])); printf ("%d\n", (int)area/100); } int main(){ while(~scanf("%d",&n)){ if(n == 1||n == 2) { printf("0\n");continue;} init(); Graham(); sov(); } }