제출 #4775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4775		gs13068	생물 실험 (IZhO13_expgorl)	C++98	100 / 100	32 ms	1276 KiB

expgorl

#include<cstdio>
#include<cmath>
#include<cstring>

char str[20000];
int x[20000];
int y[20000];

inline double dist(int x,int y)
{
	return sqrt(1LL*x*x+1LL*y*y);
}

int main()
{
	int a,b,c,d;
	int i,j,n,k;
	int l,r,t1,t2;
	double min=1.0E6,max=0.0,temp;
	scanf("%d%s%d%d%d%d",&k,str+1,&a,&b,&c,&d);
	n=strlen(str+1);
	x[0]=c-a;
	y[0]=d-b;
	for(i=1;i<=n;i++)
	{
		x[i]=x[i-1];
		y[i]=y[i-1];
		switch(str[i])
		{
		case 'L':
			x[i]--;
			break;
		case 'R':
			x[i]++;
			break;
		case 'F':
			y[i]++;
			break;
		case 'B':
			y[i]--;
			break;
		default:
			break;
		}
	}
	for(i=0;i<=n;i++)
	{
		l=0;
		r=k-1;
		while(r-l>10)
		{
			t1=(2*l+r)/3;
			t2=(l+2*r)/3;
			if(dist(x[i]+(x[n]-x[0])*t1,y[i]+(y[n]-y[0])*t1)>dist(x[i]+(x[n]-x[0])*t2,y[i]+(y[n]-y[0])*t2))
				l=t1;
			else
				r=t2;
		}
		for(j=(l-100>0?l-100:0);j<(r+100<k?r+100:k);j++)
		{
			temp=dist(x[i]+(x[n]-x[0])*j,y[i]+(y[n]-y[0])*j);
			if(temp<min)min=temp;
		}
		temp=dist(x[i],y[i]);
		if(temp>max)max=temp;
		temp=dist(x[i]+(x[n]-x[0])*(k-1),y[i]+(y[n]-y[0])*(k-1));
		if(temp>max)max=temp;
	}
	printf("%.20f %.20f",min,max);
}

• Subtask 1: 100 / 100