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

Re:TLE为什么老是这样啊

Posted by zhangsiliang880622 at 2010-08-24 11:09:01 on Problem 2187
In Reply To:TLE为什么老是这样啊 Posted by:ACM1900 at 2010-08-10 16:32:19
改成这样过的。不止是cin的原因应该……

#include <stdio.h>
#include <math.h>
#include<algorithm>
using namespace std;

#define Max 50001

struct Point
{	int x,y;};

Point p[Max];int stack[Max];
int top,n;

int  dis(Point p1,Point p2)
{
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

int cross(Point p1,Point p2,Point p3)
{	return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);}

bool comp(Point p1,Point p2)
{	if(p1.y==p2.y)
		return p1.x<p2.x;
	else
		return p1.y<p2.y;
}
void graham()
{
int i,j;	if(n<=1)
	{	top=1;
		return ;
	}
	sort(p+1,p+n+1,comp);
	top=0;
	stack[++top]=1;
	stack[++top]=2;
	for(i=3;i<=n;++i)
	{	if(top>=2&&cross(p[stack[top-1]],p[i],p[stack[top]])>=0)--top;
		stack[++top]=i;
	}
	int temptop=top;
	stack[++top]=n-1;
	for(i=n-2;i>=1;--i)
	{	if(top>=temptop+1&&cross(p[stack[top-1]],p[i],p[stack[top]])>=0)--top;
		stack[++top]=i;
	}
	int max=-1,tem;
   for(i=1;i<=top;++i)
    {   for(j=i+1;j<=top;++j)
        {  tem=dis(p[stack[i]],p[stack[j]]);
          if( tem>max )
             max=tem;
        }
    }
   
   printf("%d\n",max);
return ;
}


int main()
{
	int i;
	while(scanf("%d",&n)!=EOF)
	{	for(i=1;i<=n;i++)
			scanf("%d %d",&p[i].x,&p[i].y);
		graham();
	}
	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