1857: [Scoi2010]传送带

1857: [Scoi2010]传送带

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 1276 Solved: 702
[Submit][Status][Discuss]

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

[Submit][Status][Discuss]

假如在AB段随意找一个点E，从E出发到CD段上一点F，再到D

确定E的时候，E -> F -> D，F点的取值显然可以三分

反过来E也可以三分，因此三分套三分就行了

第一次交才分20次。。。太少了= =

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;

typedef double DB;

struct Point{
 DB x,y; Point(){}
 Point(DB x,DB y): x(x),y(y){}
 Point operator + (const Point &b) {return Point(x + b.x,y + b.y);}
 Point operator - (const Point &b) {return Point(x - b.x,y - b.y);}
 Point operator / (const DB &t) {return Point(x / t,y / t);}
}A,B,C,D,a,b,c,d;
typedef Point Vector;

DB P,Q,R;

DB Dot(const Vector &v1,const Vector &v2) {return v1.x*v2.x + v1.y*v2.y;}
DB length(const Vector &v) {return sqrt(Dot(v,v));}

DB Calc2(Point p,Point q)
{
 return length(q - p) / R + length(D - q) / Q;
}

DB Calc1(Point p)
{
 DB ret = length(p - A) / P; c = C; d = D;
 for (int I = 0; I < 30; I++)
 {
  Vector v = d - c;
  DB r1 = Calc2(p,c + v / 3.00);
  DB r2 = Calc2(p,d - v / 3.00);
  if (r1 > r2) c = c + v / 3.00;
  else d = d - v / 3.00;
 }
 return ret + Calc2(p,c + (d - c) / 2.00);
}

Point Get_P()
{
 int x,y; cin >> x >> y;
 return Point(x,y);
}

int main()
{
 #ifdef DMC
  freopen("DMC.txt","r",stdin);
 #endif
 
 A = Get_P(); B = Get_P(); 
 C = Get_P(); D = Get_P();
 cin >> P >> Q >> R; a = A; b = B;
 for (int I = 0; I < 30; I++)
 {
  Vector v = b - a;
  DB r1 = Calc1(a + v / 3.00);
  DB r2 = Calc1(b - v / 3.00);
  if (r1 > r2) a = a + v / 3.00;
  else b = b - v / 3.00;
 }
 printf("%.2f",Calc1(a + (b - a) / 2.00));
 return 0;
}

1857: [Scoi2010]传送带