【BZOJ 4570】[SCOI2016] 妖怪

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4570

这个题,省选的时候思路一点没错啊!(╯‵□′)╯︵┻━┻
是我考试的时候心太急了,当然草稿纸太小绝对也是原因之一 (逃

就是推一推式子,发现是个凸包+对勾函数
于是搞一搞范围,求一求极值就可以辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 1000000+9;
const double INF = 1e100;
 
struct Point{
    #define Vector Point 
    int x,y;
    inline Point() {}
    inline Point(int _x, int _y):x(_x),y(_y){}
    inline bool operator < (const Point &B) const{return (x<B.x)||(x==B.x&&y<B.y);}
    inline Point operator - (const Point &B) {Point C; C.x=x-B.x; C.y=y-B.y; return C;}
    inline LL operator * (const Point &B) {return (LL)x*B.y - (LL)y*B.x;}
}p[N],con[N];
int n,cnt;
double vout = INF;
 
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void ConvexHull(){
    con[++cnt] = p[n];
    for (int i=n-1;i;i--) {
        while (cnt > 1 && (con[cnt]-con[cnt-1])*(p[i]-con[cnt-1]) <= 0LL) cnt--;
        con[++cnt] = p[i];
    }
    while (cnt > 1 && con[cnt].y <= con[cnt-1].y) cnt--;
}
 
int main(){
    n = read();
    for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
    sort(p+1,p+1+n); ConvexHull(); double R, L=INF, MN;
    for (int i=1;i<=cnt;i++) {
        Vector v = con[i+1] - con[i];
        swap(L, R); L = i!=cnt?(double)-v.y / v.x:0;
        MN = sqrt((double)con[i].y / con[i].x);
        if (R < MN) vout = min(vout, con[i].x*R + con[i].y/R + con[i].x + con[i].y);
        else if (L > MN) vout = min(vout, con[i].x*L + con[i].y/L + con[i].x + con[i].y);
        else vout = min(vout, con[i].x*MN + con[i].y/MN + con[i].x + con[i].y);
    } printf("%.4lf\n",vout);
    return 0;
}

【NOI六连测】[D1T2] 过河

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18247944/
数据传送门:http://pan.baidu.com/s/1nvGnd8H

这个题目,第一眼看到的时候,一脸懵逼
后来仔细想了一想,成了二脸懵逼QAQ
于是写了30分的暴力,还好没写挂……

后来听题解,感觉很神
首先是结论:最优解时,所有的F(Xy)的斜率相等
这个按照原教的说法:
如果斜率不等,那么将斜率较低的河流的时间分一点给斜率较高的河流
我们就可以走得更远!
还是比较显然的吧!但是像我这种沙茶在考试的时候肯定想不出来QAQ
接下来就是怎么让斜率一样了。
原教又给了一个非常神的办法:
根据F’(Xy)的表达式可以得到,t随F’(Xy)的增加而减少,所以我们可以二分统一的斜率,然后判一判时间知否足够。
详细的推导如下:
\(
\begin{array}{l}
\partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\
= {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}
\end{array}
\)
不妨设\(k = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}\)
则有\(\begin{array}{l}
{u^4} \cdot {t^2} = {(k – {V_i})^2} \cdot ({u^2} \cdot {t^2} – W_i^2)\\
{t^2} \cdot ({u^4} – {(k – {V_i})^2} \cdot {u^2}) = – {(k – {V_i})^2} \cdot W_i^2\\
t = \sqrt {\frac{{{{(k – {V_i})}^2} \cdot W_i^2}}{{{{(k – {V_i})}^2} \cdot {u^2} – {u^4}}}}
\end{array}\)
所以t随k的增大而减小,且\(k \in (\max ({V_i}) + u, + \infty ]\)
之后代码就没有什么难度啦!

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define LD long double
using namespace std;

const int MAXN = 50+9;
const LD EPS = 1e-15;

int n;
LD v[MAXN],w[MAXN],ans[MAXN];
LD disx,MXv,u,t;

inline LD cal(LD k){
	LD ret = 0; 
	for (int i=1;i<=n;i++){
		LD r = (k-v[i])*(k-v[i]);
		LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u));
		ans[i] = t; ret += t;
	}
	return ret;
}

inline double GetAns(){
	LD ret = 0;
	for (int i=1;i<=n;i++){
		LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]);
		ret += tmp+v[i]*ans[i];
	}
	return (double)sqrt(ret*ret+disx*disx);
}

int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	scanf("%d",&n); cin>>u>>t;
	for (int i=1;i<=n;i++) cin>>w[i]>>v[i],
		disx+=w[i], MXv=max(MXv,v[i]);
	if (disx/u > t) {printf("-1\n");exit(0);}
	
	LD l=u+MXv,r=1e12,mid;
	while (r-l > EPS){
		mid = (l+r)/2.0;
		if (cal(mid) < t) r = mid;
		else l = mid;
	} 
	
	printf("%.3lf\n",GetAns());
	for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]);
	return 0;
} 

另外,此题卡精度QAQ,long double的EPS都得开到1e-15