2015
04-14

# Summer holiday

Summer holiday was coming! Xiaomao went back to his hometown where he yearn day and night, his hometown has picturesque scenery. There is a big forest beside his village. There are n trees in the forest.
Now they want to across the forest with a rope (the rope won’t cross). Try to find 3 trees in this tree on the rope which can make the area of the surrounded largest. Work out the area of it.

The input will consist of several test cases. The first line contains a positive integer N（3<=N<=10^6）, the number of trees, followed N lines, each gives the (xi, yi ) coordinates.

The input will consist of several test cases. The first line contains a positive integer N（3<=N<=10^6）, the number of trees, followed N lines, each gives the (xi, yi ) coordinates.

4
0 0
1 1
0 1
1 0

0.50

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

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

#define N 100010
#define EPS 1e-7

using namespace std;

struct PO
{
double x,y;
}p[N],stk[N],o;

int top,n;
double ans;

inline PO operator -(PO a,PO b)
{
PO c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}

inline double cross(PO a,PO b,PO c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

inline int dc(double x)
{
if(x>EPS) return 1;
else if(x<-EPS) return -1;
return 0;
}

inline bool cmp(const PO &a,const PO &b)
{
if(dc(a.x-b.x)==0) return a.y<b.y;
return a.x<b.x;
}

inline double getangle(PO &a,PO &b,PO &c,PO &d)
{
return cross(o,b-a,d-c);
}

inline void read()
{
for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
}

inline void graham()
{
sort(p+1,p+1+n,cmp);
top=-1;
stk[++top]=p[1]; stk[++top]=p[2];
for(int i=3;i<=n;i++)
{
while(top>=1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
stk[++top]=p[i];
}
int tmp=top;
for(int i=n-1;i>=1;i--)
{
while(top>=tmp+1&&dc(cross(stk[top-1],stk[top],p[i]))<=0) top--;
stk[++top]=p[i];
}
}

inline void rotating_calipers()
{
ans=0.0;
for(int i=0;i<top;i++)
{
int s=i+1;
for(int j=i+1,k=1;k<top;k++,j=(j+1)%top)
{
if(s==j) s=(s+1)%top;
while(s!=i&&dc(getangle(stk[i],stk[j],stk[s],stk[(s+1)%top]))>0) s=(s+1)%top;
if(s!=i) ans=max(ans,0.5*fabs(cross(stk[i],stk[j],stk[s])));
}
}
}

inline void go()
{
graham();
rotating_calipers();
printf("%.2lf\n",ans);
}

int main()
{
while(scanf("%d",&n)!=EOF) read(),go();//HDU
//while(scanf("%d",&n)&&n!=-1) read(),go();//POJ
return 0;
}


1. 第二个方法挺不错。NewHead代表新的头节点，通过递归找到最后一个节点之后，就把这个节点赋给NewHead，然后一直返回返回，中途这个值是没有变化的，一边返回一边把相应的指针方向颠倒，最后结束时返回新的头节点到主函数。

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环