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