[SCOI2010]传送带题解

比较神的一道题，以前没有接触过三分套三分…

介绍一下我的做法。

首先，碰见这种题，第一眼一般都不知道从何下手。这时候观察题目的性质，发现所走的路径一定是$A\Rightarrow X\Rightarrow Y\Rightarrow D$，其中$X\in [A,B],Y\in[C,D].$
所以很容易想到一个暴力算法：把每一对$[x,y]$都枚举一遍即可。但是这样的时间复杂度太高了，所以需要考虑别的办法。

在手算模拟之后，可以发现$[x,y]$的枚举都是有规律性的，是一个类似函数的变化。所以考虑三分。

那么怎么三分呢？

考虑问题的简化版。给你一个点，一条线段，求到哪个点最快，各种定义依据原问题的定义。

这时候很简单，很明显就是一个函数，可以三分。

那么会发现，如果这个函数有单调性，那么问题的简化版也一定具有单调性。也就是说解也是有单调性的。

所以我们可以先三分$X$,再三分$Y$，最后选择一个最优解即可。

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define PI 3.14159265
#define DO_NOT_USE_SCANF ios::sync_with_stdio(0)
#define PQ priority_queue
#define lowbit(x) ((x) & (-x))
#define lmy
#ifdef lmy
	#define DEBUG printf("Passing [%s] in LINE %d...\n" , __FUNCTION__ , __LINE__)
#endif
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

inline void read(int &x) {
	int f = 1;x = 0;char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}

inline void readll(ll &x) {
	ll f = 1;x = 0;char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}

struct Point {
	double x , y;
};

Point a , b , c , d;

double p , q , r;

const double eps = 1e-6;
double dist(Point a , Point b) {
	return sqrt((a . x - b . x) * (a . x - b . x) + (a . y - b . y) * (a . y - b . y));
}

double f(Point x , Point y) {
	return dist(a , x) / p + dist(x , y) / r + dist(y , d) / q;
}
double task(Point x) {
	Point l = c , r = d;
	while(dist(l , r) > eps) {
		Point delta = (Point){(r . x - l . x) / 3 , (r . y - l . y) / 3};
		Point lmid = (Point){l . x + delta . x , l . y + delta . y};
		Point rmid = (Point){r . x - delta . x , r . y - delta . y};
		if(f(x , rmid) - f(x , lmid) > eps) r = rmid;
		else l = lmid;
	}
	return f(x , l);
}


void solve() {
	scanf("%lf%lf%lf%lf" , &a . x , &a . y , &b . x , &b . y);
	scanf("%lf%lf%lf%lf" , &c . x , &c . y , &d . x , &d . y);
	scanf("%lf%lf%lf" , &p , &q , &r);

	Point l = a , r = b;
	while(dist(l , r) > eps) {
		Point delta = (Point){(r . x - l . x) / 3 , (r . y - l . y) / 3};
		Point lmid = (Point){l . x + delta . x , l . y + delta . y};
		Point rmid = (Point){r . x - delta . x , r . y - delta . y};
		if(task(rmid) - task(lmid) > eps) r = rmid;
		else l = lmid;
	}

	cout << fixed << setprecision(2) << task(l) << endl;
	return;
}
int main(){
	#ifdef lmy
		int nol_cl = clock();
	#endif

	solve();

	// did you forget to undefine Lmy ?
	#ifdef lmy
		printf("\nTime: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000));
	#endif
	return 0;
}

# 三分法

[SCOI2010]传送带题解

评论

分类

Your browser is out-of-date!

[SCOI2010]传送带 题解

评论

分类

Your browser is out-of-date!

[SCOI2010]传送带题解