POJ3348-凸包

2019-11-14 09:33:31

字体：大中小

来源：转载

供稿：网友

题意：一片草地上有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(); }}

上一篇：【C++】【USACO1.1.2】贪婪的送礼者

下一篇：ChucK初步（3）