[Scoi2010]传送带

[Scoi2010]传送带

Time Limit:1000MS  Memory Limit:65536K
Total Submit:48 Accepted:30

Description

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的 移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间

Input

输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy
第三行是3个整数,分别是P,Q,R

Output

输出数据为一行,表示lxhgww从A点走到D点的最短时间,保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于100%的数据,1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

Source

Day2
很显然正解是双重二分之类的,不过我用模拟退火A掉了囧。。随机化无敌!!!
Code:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
double P,Q,R;
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
Point operator*(double d)
{
return Point(x*d,y*d);
}
Point operator+(const Point&o)const
{
return Point(x+o.x,y+o.y);
}
};
struct Line
{
Point A,B;
Line(){}
Point get(double d)
{
return A*d+B*(1-d);
}
}A,B;
istream& operator>>(istream&in,Point&p)
{
in>>p.x>>p.y;
return in;
}
istream& operator>>(istream&in,Line&l)
{
in>>l.A>>l.B;
return in;
}
struct State
{
double Up,Down;
State(){}
State(double _Up,double _Down):Up(_Up),Down(_Down){}
void Just(double a,double b)
{
Up+=a;Down+=b;
}
};
double Dist(const Point&a,const Point&b)
{
static double A,B;
A=a.x-b.x,B=a.y-b.y;
return sqrt(A*A+B*B);
}
double Cal(State s)
{
Point a=A.get(s.Up),b=B.get(s.Down);
return Dist(a,A.A)/P+Dist(a,b)/R+Dist(b,B.B)/Q;
}
double rand_double()
{
return (double(2*rand())/RAND_MAX)-1;
}
double check_Legal(State s)
{
return s.Up>=0&&s.Up<=1&&s.Down>=0&&s.Down<=1;
}
int main()
{
//freopen("in","r",stdin);
cin>>A>>B>>P>>Q>>R;
State now(0,0),tmp;double min=Cal(now);
for(double e=1;e>1e-10;e/=2)
{
int time=1000;
while(time–)
{
tmp=now;tmp.Just(rand_double()*e,rand_double()*e);
if(!check_Legal(tmp))continue;
double new_min=Cal(tmp);
if(new_min<min)
{
min=new_min;now=tmp;
}
}
}
printf("%0.2lfn",min);
}

10 thoughts on “[Scoi2010]传送带

  1. 回复中国脑筋:不是啦,到不用真求导,F'(x)差不多是F(x+eps)-F(eps)/eps,eps是个小数字,然后只要二分求这个最接近0的值就OK了。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>