| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1763 求bug#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct point
{
int x,y,n;
}p[250010];
bool cmp1(const point & a,const point &b)
{
if(a.x>b.x||(a.x==b.x)&&(a.y>b.y))return false;
else return true;
}
bool cmp2(const point & a,const point &b)
{
if(a.y>b.y||(a.y==b.y)&&(a.x>b.x))return false;
else return true;
}
int minl(int a,int b)
{
return a<b?a:b;
}
int maxl(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,k,n,x,y,minx,maxy;
char ch;
cin>>j;
x=0;
y=0;
n=0;
for(i=0;i<j;i++)
{
cin>>ch;
p[n].x=x;
p[n].y=y;
p[n].n=i;
if(ch=='N')y++;
if(ch=='S')y--;
if(ch=='W')x--;
if(ch=='E')x++;
n++;
}
p[n].x=x;
p[n].y=y;
p[n++].n=j;
sort(p,p+n,cmp1);
k=300000;
x=300000;
y=-1;
for(i=0;i<n;i++)
{
if(p[i].x==p[i+1].x)
{
j=abs(p[i].y-p[i+1].y);
minx=minl(p[i].n,p[i+1].n);
maxy=maxl(p[i].n,p[i+1].n);
if(maxy-minx>j)
{
if(k>j||(k==j&&minx<x)||(k==j&&minx==x&&maxy>y))
{
k=j;
x=minx;
y=maxy;
}
}
}
}
sort(p,p+n,cmp2);
for(i=0;i<n;i++)
{
if(p[i].y==p[i+1].y)
{
j=abs(p[i].x-p[i+1].x);
minx=minl(p[i].n,p[i+1].n);
maxy=maxl(p[i].n,p[i+1].n);
if(maxy-minx>j)
{
if(k>j||(k==j&&minx<x)||(k==j&&minx==x&&maxy>y))
{
k=j;
x=minx;
y=maxy;
}
}
}
}
cout<<k<<' '<<x<<' '<<y;
for(i=0;i<n;i++)
{
if(x==p[i].n)x=i;
if(y==p[i].n)y=i;
}
if(p[x].x<p[y].x)cout<<" E"<<endl;
if(p[x].x>p[y].x)cout<<" W"<<endl;
if(p[x].y<p[y].y)cout<<" N"<<endl;
if(p[x].y>p[y].y)cout<<" S"<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator