Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1763 求bug

Posted by anlan at 2010-03-10 08:49:29 on Problem 1763
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator