題意：一片草地上有n課樹，現在你想用繩子圈出一個盡可能大的面積出來養牛。已知每只牛需要50單位的面積，問最多能養幾只牛。
從小到大遍歷，走到最大是一半的凸包，然后從大到小在走一遍，另半個凸包
#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(); }}新聞熱點
疑難解答
