学步园

题目大意：给你n个杠子，m个x单调递增的点（就是地形），再给你阳光的偏角a，求最大的被阳光照到的长度（地形和杠子都会挡住阳光），以及杠子放的位置（杠子只能竖直放置） n<=10000 m<=10000 0<a<90

这道题有几种写法，一种是坐标转换的 传送门：http://blog.csdn.net/u012647218/article/details/42714121

还有不是坐标转换的，首先找到最长的那根杆子，先不用着，然后把剩下的杠子一路放过来，具体来说就是先在最前面放一根杆子，然后看太阳光的阴影到哪，就把下一根放哪，直到没有杆子或者没有地方放为止。至于最后那根最高的杠子，就放在最后一根所放的后方（不挡住其余的）且受益最大的地方就OK了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10011;
const double pai=M_PI,eps=1e-6;
struct Tp{double x,y;}e[maxn];
struct Tl{double a,b,c;};
double h[maxn]; int n,m; double sk;
void init(){
	int a; scanf("%d",&a); sk=tan(-a*pai/180);
	for (int i=1;i<=n;++i) scanf("%lf",h+i);
	for (int i=1;i<=m;++i) scanf("%lf%lf",&e[i].x,&e[i].y);
}
int sgn(double x){
	if (x+eps>0 && x-eps<0) return 0;
	if (x-eps>0) return 1; return -1;
}
Tp w[maxn]; double *p[maxn];
Tp getp(Tl l1,Tl l2){
	if (!sgn(l1.a-l2.a)){
		double tmp=l2.a/l1.a; l1.b*=tmp; l1.c*=tmp;
		Tp o; o.y=(l2.c-l1.c)/(l1.b-l2.b); o.x=(l2.c+o.y*l2.b)/(-l2.a); return o;
	}else{
		double tmp=l2.b/l1.b; l1.a*=tmp; l1.c*=tmp;
		Tp o; o.x=(l2.c-l1.c)/(l1.a-l2.a); o.y=(l2.c+o.x*l2.a)/(-l2.b); return o;
	}
}
Tl getl(Tp x,double k){Tl l; l.a=k; l.b=-1; l.c=-x.x*k+x.y; return l;}
Tl getl(Tp a,Tp b){double k=(b.y-a.y)/(b.x-a.x); return getl(a,k);}
Tp getp(Tp x,Tp a,Tp b){Tl l1=getl(x,sk),l2=getl(a,b); return getp(l1,l2);}
bool check(Tp x,Tp a,Tp b){Tp o=getp(x,a,b); return o.x+eps>a.x && o.x-eps<b.x;}
double gety(Tp a,double x){
	Tl l=getl(a,sk); return (l.c+l.a*x)/(-l.b);
}
string a=""; char xxx[100],*tmp=xxx;
inline bool cmp(double *a,double *b){return *a<*b;}
void work(){
	for (int i=1;i<=n;++i) p[i]=h+i; sort(p+1,p+n+1,cmp);
	double ans=0; Tp last=e[1]; int now=1;
	for (int i=1;i<=n;++i){
		w[p[i]-h]=last; ans+=*p[i]; last.y+=*p[i]; int ln=now;
		while (now<m && !check(last,e[now],e[now+1])) ++now;
		if (now<m) last=getp(last,e[now],e[now+1]);
		else if (i<n){
			int tm=m;
			for (int x=ln+1;x<m;++x)
				if ((e[x].y-gety(last,e[x].x))>(e[tm].y-gety(last,e[tm].x))) tm=x;
			if (*p[n]-*p[i]>e[tm].y+*p[n]-gety(last,e[tm].x)){
				ans+=*p[n]-*p[i];
				for (++i;i<=n;++i) w[p[i]-h]=last;
			}else{
				ans+=e[tm].y+*p[n]-gety(last,e[tm].x);
				for (++i;i<=n;++i) w[p[i]-h]=e[tm];
			}
		}
	}
	printf("%.7f\n",ans);
	for (int i=1;i<=n;++i) printf("%.10f\n",w[i].x);
}
int main(){
	while (scanf("%d%d",&n,&m)!=EOF) init(),work();
	return 0;
}