POJ 2079/HDU 3934 旋转卡壳

题意：

给一些点，任选任选三个构成三角形，求这个三角形的最大面积。

题解：
旋转卡壳，水题了。。

n^2明显的过不了的，但是数据水，能过。

有没有nlogn的算法啊？？

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 #define N 100010
  9 #define EPS 1e-7
 10 
 11 using namespace std;
 12 
 13 struct PO
 14 {
 15     double x,y;
 16 }p[N],stk[N],o;
 17 
 18 int top,n;
 19 double ans;
 20 
 21 inline PO operator -(PO a,PO b)
 22 {
 23     PO c;
 24     c.x=a.x-b.x;
 25     c.y=a.y-b.y;
 26     return c;
 27 }
 28 
 29 inline double cross(PO a,PO b,PO c)
 30 {
 31     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
 32 }
 33 
 34 inline int dc(double x)
 35 {
 36     if(x>EPS) return 1;
 37     else if(x<-EPS) return -1;
 38     return 0;
 39 }
 40 
 41 inline bool cmp(const PO &a,const PO &b)
 42 {
 43     if(dc(a.x-b.x)==0) return a.y<b.y;
 44     return a.x<b.x;
 45 }
 46 
 47 inline double getangle(PO &a,PO &b,PO &c,PO &d)
 48 {
 49     return cross(o,b-a,d-c);
 50 }
 51 
 52 inline void read()
 53 {
 54     for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
 55 }
 56 
 57 inline void graham()
 58 {
 59     sort(p+1,p+1+n,cmp);
 60     top=-1;
 61     stk[++top]=p[1]; stk[++top]=p[2];
 62     for(int i=3;i<=n;i++)
 63     {
 64         while(top>=1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
 65         stk[++top]=p[i];
 66     }
 67     int tmp=top;
 68     for(int i=n-1;i>=1;i--)
 69     {
 70         while(top>=tmp+1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
 71         stk[++top]=p[i];
 72     }
 73 }
 74 
 75 inline void rotating_calipers()
 76 {
 77     ans=0.0;
 78     for(int i=0;i<top;i++)
 79     {
 80         int s=i+1;
 81         for(int j=i+1,k=1;k<top;k++,j=(j+1)%top)
 82         {
 83             if(s==j) s=(s+1)%top;
 84             while(s!=i&&dc(getangle(stk[i],stk[j],stk[s],stk[(s+1)%top]))>0) s=(s+1)%top;
 85             if(s!=i) ans=max(ans,0.5*fabs(cross(stk[i],stk[j],stk[s])));
 86         }
 87     }
 88 }
 89 
 90 inline void go()
 91 {
 92     graham();
 93     rotating_calipers();
 94     printf("%.2lf\n",ans);
 95 }
 96 
 97 int main()
 98 {
 99     while(scanf("%d",&n)!=EOF) read(),go();//HDU
100     //while(scanf("%d",&n)&&n!=-1) read(),go();//POJ
101     return 0;
102 }

一个代码交两个OJ真是爽~