HDU 2993 MAX Average Problem

给Wordpress换了个Ckeditor，这篇文章的目地主要是想测试一下代码高亮。。。

不过默认提供的几种风格每一个我喜欢的（还是最喜欢vim风格)，还是将就一下吧。。。

斜率优化的经典基础题，具体方法什么的自己去看周源的WC论文

http://acm.hdu.edu.cn/showproblem.php?pid=2993

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef long long int64;

struct point{
	int64 x,y;
} st[200000],t;
int n,k,sum[200000],top;

inline int det(int64 x1,int64 y1,int64 x2,int64 y2){
	int64  s=x1*y2-y1*x2;
	return s>0?1:(!s?0:-1);
}

inline int cross(struct point a,struct point b,struct point c,struct point d){
	return det(b.x-a.x, b.y-a.y, d.x-c.x, d.y-c.y);
}

inline double calk(struct point a,struct point b){
	return (double)(b.y-a.y)/(b.x-a.x);
}

int main(){
	while(~scanf("%d %d\n",&n,&k)){
		int a,b,c;top=0;char ch;
		for(int i=1;i<=n;i++){
			a=0;
			while(ch=getchar(),ch<'0'||ch>'9');
			a=ch-'0';
			while(ch=getchar(),ch>='0'&&ch<='9') a=a*10+ch-'0';
			sum[i]=sum[i-1]+a;
		}
		double ans=0,tmp;
		int last=0,i,j;
		for(i=1;i<=n;i++){		
			if(i-k>=0){
				t.x=i-k;t.y=sum[i-k];
				while(top>1&&cross(st[top-2],st[top-1],st[top-1],t)<0)	top--;
				st[top++]=t;
			}
			if(top<=0)	continue;
			t.x=i;t.y=sum[i];
			if(last>=top-1)	last=top-1;
			for(j=last;j<top-1;j++)
				if(cross(st[j],t,st[j+1],t)<0)	break;	
			last=j;tmp=calk(st[j],t);
			ans=max(ans,tmp);
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

注意几个坑爹的地方

1.数据量超大，直接scanf读入O(n)算法一样TLE，要自己手动写读入。。。

2.用叉乘判方向时注意要开到long long

3.这题其实没有精度问题，double算斜率再直接比较一样也行，而且比叉乘判断要快

4.实际运行时在凹曲线内的包含点数很少，O(n²)枚举凹曲线上的点也不会TLE