#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2005000
#define MOD 1000000007
#define N 300005
#define M 1000005
#define LOG 18
#define KOK 4000000
using namespace std;
int k,n,lx,ly,gx,gy,igmn[N],igmx[N];
double amin=inf,amax=-inf;
vector<ii> po;
char s[N];
double gds(ii x,ii y) {
return sqrt(1ll*(x.st-y.st)*(x.st-y.st)+1ll*(x.nd-y.nd)*(x.nd-y.nd));
}
void try_max(int ind) {
ii cur=po[ind];
umax(amax,gds(cur,{lx,ly}));
for(int i=1;i<=n;i++) {
if(s[i]=='L') cur.st--;
if(s[i]=='R') cur.st++;
if(s[i]=='F') cur.nd++;
if(s[i]=='B') cur.nd--;
umax(amax,gds(cur,{lx,ly}));
}
}
void try_min(int ind) {
ii cur=po[ind];
umin(amin,gds(cur,{lx,ly}));
for(int i=1;i<=n;i++) {
if(s[i]=='L') cur.st--;
if(s[i]=='R') cur.st++;
if(s[i]=='F') cur.nd++;
if(s[i]=='B') cur.nd--;
umin(amin,gds(cur,{lx,ly}));
}
}
int fmax() {
double dist=-inf;
int ret;
for(int i=0;i<sz(po);i++) {
if(igmx[i]) continue ;
double cur=gds(po[i],{lx,ly});
if(dist<cur) {
dist=cur;
ret=i;
}
}
return ret;
}
int fmin() {
double dist=inf;
int ret;
for(int i=0;i<sz(po);i++) {
if(igmn[i]) continue ;
double cur=gds(po[i],{lx,ly});
if(dist>cur) {
dist=cur;
ret=i;
}
}
return ret;
}
int main() {
// freopen("input.txt","r",stdin);
scanf("%d",&k);
scanf("%s",s+1);
n=strlen(s+1);
scanf("%d %d",&lx,&ly);
scanf("%d %d",&gx,&gy);
int px=0,py=0;
for(int i=1;i<=n;i++) {
if(s[i]=='L') px--;
if(s[i]=='R') px++;
if(s[i]=='F') py++;
if(s[i]=='B') py--;
}
po.pb({gx+px,gy+py});
for(int i=1;i<k;i++) {
po.pb({po.back().st+px,po.back().nd+py});
}
int magic=min(k,k);
for(int i=1;i<=magic;i++) {
int pmin=fmin();
int pmax=fmax();
try_min(pmin);
try_max(pmax);
igmn[pmin]=1;
igmx[pmax]=1;
}
printf("%.12lf %.12lf\n",amin,amax);
}
Compilation message
expgorl.cpp: In function 'int main()':
expgorl.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
~~~~~^~~~~~~~~
expgorl.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);
~~~~~^~~~~~~~~~
expgorl.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&lx,&ly);
~~~~~^~~~~~~~~~~~~~~~~
expgorl.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&gx,&gy);
~~~~~^~~~~~~~~~~~~~~~~
expgorl.cpp: In function 'int fmax()':
expgorl.cpp:95:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ret;
^~~
expgorl.cpp: In function 'int fmin()':
expgorl.cpp:119:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ret;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1077 ms |
760 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
