|
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
struct xl
{
double x,y;
}v[1001];
double dis(int i, int j)
{
return sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
}
int main()
{
int t,n,s,tmp,i,id[1001],l[1001],w,res;
double p,q;
RD(t);
while(t--)
{
scanf("%d%d%d%lf%lf",&n,&s,&tmp,&p,&q);
p+=q;
FOR(1,n,i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
id[i]=-1;
}
id[s]=0;
l[0]=s;
w=1;
res=0;
while(res
{
s=l[res];
FOR(1,n,i)
{
if(id[i]<0&&dis(s,i)
{
id[i]=id[s]+1;
l[w++]=i;
if(i==tmp)
{
break;
}
}
}
res++;
}
if(id[tmp]>=0)
{
printf("%d\n",id[tmp]);
}
else
{
printf("Impossible\n");
}
}
return 0;
}
I.Shortest Leash
应该是一道dp题，它要求狗可以选择多个向量的正负方向走，问最远能与远点的距离为多少。。。
我是用随机算法过的，目的在于将所有的向量打乱，使其在加上向量时，能够会在一次中找到正解。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i
using namespace std;
struct xl
{
double x,y;
} p[101],q,l,r;
double dis(xl a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
int main()
{
int t,i,j,z[101];
double ans;
while(scanf("%d",&t))
{
if(t==0)
{
break;
}
for(i=0; i
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
ans=0;
for(j=0;j<=10000;++j)
{
random_shuffle(p,p+t);//随机打乱数组
q.x=0;
q.y=0;
for(i=0; i
{
l=q;
r=q;
l.x+=p[i].x;
l.y+=p[i].y;
r.x-=p[i].x;
r.y-=p[i].y;
if(dis(l)>dis(r))
{
q=l;
}
else
{
q=r;
}
ans=max(ans,dis(q));
}
}
printf("%.3f\n",ans);
}
|