#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 2005000000
#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,gy});
for(int i=1;i<k;i++) {
po.pb({po.back().st+px,po.back().nd+py});
}
int magic=min(k,100);
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;
//try_min(i-1);
//try_max(i-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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
760 KB |
Output is correct |
| 2 |
Correct |
40 ms |
760 KB |
Output is correct |
| 3 |
Correct |
39 ms |
760 KB |
Output is correct |
| 4 |
Correct |
40 ms |
788 KB |
Output is correct |
| 5 |
Correct |
33 ms |
788 KB |
Output is correct |
| 6 |
Correct |
42 ms |
868 KB |
Output is correct |
| 7 |
Correct |
33 ms |
868 KB |
Output is correct |
| 8 |
Correct |
46 ms |
1056 KB |
Output is correct |
| 9 |
Correct |
218 ms |
1704 KB |
Output is correct |
| 10 |
Correct |
197 ms |
1704 KB |
Output is correct |
| 11 |
Correct |
198 ms |
1712 KB |
Output is correct |
| 12 |
Correct |
136 ms |
1712 KB |
Output is correct |
| 13 |
Correct |
142 ms |
1712 KB |
Output is correct |
| 14 |
Correct |
173 ms |
1748 KB |
Output is correct |
| 15 |
Correct |
205 ms |
1816 KB |
Output is correct |
| 16 |
Correct |
236 ms |
1824 KB |
Output is correct |
| 17 |
Correct |
235 ms |
1848 KB |
Output is correct |
| 18 |
Correct |
239 ms |
1864 KB |
Output is correct |
| 19 |
Correct |
239 ms |
1876 KB |
Output is correct |
| 20 |
Correct |
238 ms |
1888 KB |
Output is correct |
