[Scoi2010]\u4f20\u9001\u5e26 <\/p>\n
Time Limit:1000MS Memory Limit:65536K
Total Submit:48 Accepted:30<\/p>\n
Description <\/strong><\/p>\n \u5728\u4e00\u4e2a2\u7ef4\u5e73\u9762\u4e0a\u6709\u4e24\u6761\u4f20\u9001\u5e26\uff0c\u6bcf\u4e00\u6761\u4f20\u9001\u5e26\u53ef\u4ee5\u770b\u6210\u662f\u4e00\u6761\u7ebf\u6bb5\u3002\u4e24\u6761\u4f20\u9001\u5e26\u5206\u522b\u4e3a\u7ebf\u6bb5AB\u548c\u7ebf\u6bb5CD\u3002lxhgww\u5728AB\u4e0a\u7684\u79fb\u52a8\u901f\u5ea6\u4e3aP\uff0c\u5728CD\u4e0a\u7684 \u79fb\u52a8\u901f\u5ea6\u4e3aQ\uff0c\u5728\u5e73\u9762\u4e0a\u7684\u79fb\u52a8\u901f\u5ea6R\u3002\u73b0\u5728lxhgww\u60f3\u4eceA\u70b9\u8d70\u5230D\u70b9\uff0c\u4ed6\u60f3\u77e5\u9053\u6700\u5c11\u9700\u8981\u8d70\u591a\u957f\u65f6\u95f4 <\/p>\n Input <\/strong><\/p>\n \u8f93\u5165\u6570\u636e\u7b2c\u4e00\u884c\u662f4\u4e2a\u6574\u6570\uff0c\u8868\u793aA\u548cB\u7684\u5750\u6807\uff0c\u5206\u522b\u4e3aAx\uff0cAy\uff0cBx\uff0cBy Output <\/strong><\/p>\n \u8f93\u51fa\u6570\u636e\u4e3a\u4e00\u884c\uff0c\u8868\u793alxhgww\u4eceA\u70b9\u8d70\u5230D\u70b9\u7684\u6700\u77ed\u65f6\u95f4\uff0c\u4fdd\u7559\u5230\u5c0f\u6570\u70b9\u540e2\u4f4d <\/p>\n Sample Input <\/strong><\/p>\n 0 0 0 100 Sample Output <\/strong><\/p>\n 136.60<\/p>\n Hint <\/strong><\/p>\n \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c1<= Ax\uff0cAy\uff0cBx\uff0cBy\uff0cCx\uff0cCy\uff0cDx\uff0cDy<=1000 Source <\/strong><\/p>\n Day2 #include <vector> [Scoi2010]\u4f20\u9001\u5e26 Time Limit:1000MS Memory Limit:65536KTotal Submit:48 Accepted:30 Description \u5728\u4e00\u4e2a2\u7ef4\u5e73\u9762\u4e0a\u6709\u4e24\u6761\u4f20\u9001\u5e26\uff0c\u6bcf\u4e00\u6761\u4f20\u9001\u5e26\u53ef\u4ee5\u770b\u6210\u662f\u4e00\u6761\u7ebf\u6bb5\u3002\u4e24\u6761\u4f20\u9001\u5e26\u5206\u522b\u4e3a\u7ebf\u6bb5AB\u548c\u7ebf\u6bb5CD\u3002lxhgww\u5728AB\u4e0a\u7684\u79fb\u52a8\u901f\u5ea6\u4e3aP\uff0c\u5728CD\u4e0a\u7684 \u79fb\u52a8\u901f\u5ea6\u4e3aQ\uff0c\u5728\u5e73\u9762\u4e0a\u7684\u79fb\u52a8\u901f\u5ea6R\u3002\u73b0\u5728lxhgww\u60f3\u4eceA\u70b9\u8d70\u5230D\u70b9\uff0c\u4ed6\u60f3\u77e5\u9053\u6700\u5c11\u9700\u8981\u8d70\u591a\u957f\u65f6\u95f4 Input \u8f93\u5165\u6570\u636e\u7b2c\u4e00\u884c\u662f4\u4e2a\u6574\u6570\uff0c\u8868\u793aA\u548cB\u7684\u5750\u6807\uff0c\u5206\u522b\u4e3aAx\uff0cAy\uff0cBx\uff0cBy \u7b2c\u4e8c\u884c\u662f4\u4e2a\u6574\u6570\uff0c\u8868\u793aC\u548cD\u7684\u5750\u6807\uff0c\u5206\u522b\u4e3aCx\uff0cCy\uff0cDx\uff0cDy \u7b2c\u4e09\u884c\u662f3\u4e2a\u6574\u6570\uff0c\u5206\u522b\u662fP\uff0cQ\uff0cR Output \u8f93\u51fa\u6570\u636e\u4e3a\u4e00\u884c\uff0c\u8868\u793alxhgww\u4eceA\u70b9\u8d70\u5230D\u70b9\u7684\u6700\u77ed\u65f6\u95f4\uff0c\u4fdd\u7559\u5230\u5c0f\u6570\u70b9\u540e2\u4f4d Sample Input 0 0 0 100100 0 100 1002 2 1 Sample Output 136.60 Hint \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c1<= Ax\uff0cAy\uff0cBx\uff0cBy\uff0cCx\uff0cCy\uff0cDx\uff0cDy<=1000 1<=P\uff0cQ\uff0cR<=10 Source Day2\u5f88\u663e\u7136\u6b63\u89e3\u662f\u53cc\u91cd\u4e8c\u5206\u4e4b\u7c7b\u7684\uff0c\u4e0d\u8fc7\u6211\u7528\u6a21\u62df\u9000\u706bA\u6389\u4e86\u56e7\u3002\u3002\u968f\u673a\u5316\u65e0\u654c\uff01\uff01\uff01Code\uff1a #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_backconst int inf=~0U>>1;using namespace std;typedef long long […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/266"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=266"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/266\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u7b2c\u4e8c\u884c\u662f4\u4e2a\u6574\u6570\uff0c\u8868\u793aC\u548cD\u7684\u5750\u6807\uff0c\u5206\u522b\u4e3aCx\uff0cCy\uff0cDx\uff0cDy
\u7b2c\u4e09\u884c\u662f3\u4e2a\u6574\u6570\uff0c\u5206\u522b\u662fP\uff0cQ\uff0cR <\/p>\n
100 0 100 100
2 2 1<\/p>\n
1<=P\uff0cQ\uff0cR<=10 <\/p>\n
\u5f88\u663e\u7136\u6b63\u89e3\u662f\u53cc\u91cd\u4e8c\u5206\u4e4b\u7c7b\u7684\uff0c\u4e0d\u8fc7\u6211\u7528\u6a21\u62df\u9000\u706bA\u6389\u4e86\u56e7\u3002\u3002\u968f\u673a\u5316\u65e0\u654c\uff01\uff01\uff01
Code\uff1a<\/p>\n
#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);
}<\/p>\n","protected":false},"excerpt":{"rendered":"